Search in Rotated Sorted Array in DSA Java

Mental Model

We look for a number in a sorted list that has been turned around at some point. We use a smart search that checks which part is sorted to decide where to look next.

Analogy: Imagine a circularly arranged bookshelf where books are sorted alphabetically but the start is somewhere in the middle. To find a book, you check which half of the shelf is in order and decide which half to search next.

Array: 4 -> 5 -> 6 -> 7 -> 0 -> 1 -> 2 -> null
Indices: [0]  [1]  [2]  [3]  [4]  [5]  [6]

Dry Run Walkthrough

Input: array: [4,5,6,7,0,1,2], target: 0

Goal: Find the index of target 0 in the rotated sorted array

Step 1: Set low=0, high=6, mid=(0+6)/2=3, check value at mid=7

Array: 4 -> 5 -> 6 -> [7] -> 0 -> 1 -> 2 -> null
Indices: [0]  [1]  [2]  [3]  [4]  [5]  [6]

Why: We start searching in the middle to split the array

Step 2: Check if left half [4..7] is sorted: yes (4 ≤ 7). Check if target 0 is in [4..7]: no

Same as step 1

Why: Since target is not in sorted left half, search right half

Step 3: Set low=mid+1=4, high=6, mid=(4+6)/2=5, check value at mid=1

Array: 4 -> 5 -> 6 -> 7 -> 0 -> [1] -> 2 -> null
Indices: [0]  [1]  [2]  [3]  [4]  [5]  [6]

Why: Focus search on right half where target might be

Step 4: Check if left half [0..1] is sorted: yes (0 ≤ 1). Check if target 0 is in [0..1]: yes

Same as step 3

Why: Target is in sorted left half, so search there

Step 5: Set low=4, high=mid-1=4, mid=(4+4)/2=4, check value at mid=0

Array: 4 -> 5 -> 6 -> 7 -> [0] -> 1 -> 2 -> null
Indices: [0]  [1]  [2]  [3]  [4]  [5]  [6]

Why: Narrow search to left half to find target

Step 6: Value at mid equals target 0, return index 4

Same as step 5

Why: Found the target, stop searching

Result:

4 -> 5 -> 6 -> 7 -> [0] -> 1 -> 2 -> null
Target 0 found at index 4

Annotated Code

DSA Java

public class RotatedSortedArraySearch {
    public static int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                return mid; // found target
            }
            // Check if left half is sorted
            if (nums[low] <= nums[mid]) {
                // Target in left half?
                if (nums[low] <= target && target < nums[mid]) {
                    high = mid - 1; // search left
                } else {
                    low = mid + 1; // search right
                }
            } else {
                // Right half is sorted
                if (nums[mid] < target && target <= nums[high]) {
                    low = mid + 1; // search right
                } else {
                    high = mid - 1; // search left
                }
            }
        }
        return -1; // target not found
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        int target = 0;
        int index = search(nums, target);
        System.out.println(index);
    }
}

while (low <= high) {

loop to narrow search range until low passes high

int mid = low + (high - low) / 2;

calculate middle index to check

if (nums[mid] == target) { return mid; }

if middle element is target, return index

if (nums[low] <= nums[mid]) {

check if left half is sorted

if (nums[low] <= target && target < nums[mid]) { high = mid - 1; } else { low = mid + 1; }

decide to search left or right half based on target position

else { if (nums[mid] < target && target <= nums[high]) { low = mid + 1; } else { high = mid - 1; } }

if right half is sorted, decide search side similarly

Output

4

Complexity Analysis

Time: O(log n) because each step halves the search space by checking sorted halves

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Compared to linear search O(n), this binary search approach is much faster on large arrays

Edge Cases

empty array

returns -1 immediately because low > high

DSA Java

while (low <= high) {

array with one element equal to target

returns index 0 immediately

DSA Java

if (nums[mid] == target) { return mid; }

target not in array

returns -1 after search space is exhausted

DSA Java

return -1; // target not found

When to Use This Pattern

When you see a sorted array that has been rotated and need to find an element quickly, use this pattern of checking which half is sorted to guide a binary search.

Common Mistakes

Mistake: Not checking which half is sorted before deciding where to search next
Fix: Always check if left half or right half is sorted to correctly narrow search

Mistake: Using regular binary search without adjusting for rotation
Fix: Modify binary search to handle rotation by comparing low, mid, and high values

Summary

Finds the index of a target in a rotated sorted array using modified binary search.

Use when you have a sorted array rotated at some pivot and need fast search.

The key is to identify which half is sorted to decide where the target can be.

Practice

1. What is the main challenge when searching for an element in a rotated sorted array compared to a normal sorted array?

easy

A. The array elements are all negative numbers.

B. The array contains duplicate elements which confuse the search.

C. The array is not fully sorted, so normal binary search cannot be directly applied.

D. The array size is unknown, so we cannot set search boundaries.

Solution

1. Step 1: Understand normal binary search assumption

   Binary search works efficiently only if the array is fully sorted in ascending or descending order.

2. Step 2: Identify the effect of rotation

   Rotation breaks the full sorted order, splitting the array into two sorted parts, so normal binary search fails without modification.

3. Final Answer:

   The array is not fully sorted, so normal binary search cannot be directly applied. -> Option C

4. Quick Check:

   Rotated array breaks full sort = normal binary search fails [OK]

Hint: Rotation breaks full sort; adjust binary search accordingly [OK]

Common Mistakes:

• Assuming array is fully sorted and applying normal binary search
• Ignoring rotation and searching linearly
• Confusing rotation with duplicates

2. Which of the following is the correct Java method signature to implement binary search in a rotated sorted array?

easy

A. int search(int nums[], target)

B. public int search(int[] nums, int target)

C. public void search(int[] nums, int target)

D. int search(int[] nums, int target, int start, int end)

Solution

1. Step 1: Check Java method signature conventions

   Java methods must specify access modifier, return type, method name, and parameter types with names.

2. Step 2: Analyze each option

   public int search(int[] nums, int target) correctly declares a public method returning int with parameters int[] and int. int search(int nums[], target) misses return type and parameter type for target. public void search(int[] nums, int target) returns void but search should return index. int search(int[] nums, int target, int start, int end) has extra parameters but no access modifier.

3. Final Answer:

   public int search(int[] nums, int target) -> Option B

4. Quick Check:

   Correct Java method signature = public int search(int[] nums, int target) [OK]

Hint: Java method needs return type and parameter types correctly [OK]

Common Mistakes:

• Omitting return type
• Missing parameter types
• Using void instead of int return type

3. What will be the output of the following Java code snippet?

public class RotatedSearch {
    public static int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) right = mid - 1;
                else left = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] arr = {4,5,6,7,0,1,2};
        System.out.println(search(arr, 0));
    }
}

medium

A. 4

B. 0

C. -1

D. 6

Solution

1. Step 1: Understand the array and target

   The array is rotated sorted: [4,5,6,7,0,1,2]. Target is 0, which is at index 4.

2. Step 2: Trace the binary search steps

   Initial left=0, right=6, mid=3 (value 7). Left half is sorted (4 to 7). Target 0 is not in left half, so move left=mid+1=4. Now left=4, right=6, mid=5 (value 1). Right half is sorted (1 to 2). Target 0 is less than nums[mid], so move right=mid-1=4. Now left=4, right=4, mid=4 (value 0). Found target at index 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Target 0 found at index 4 [OK]

Hint: Check which half is sorted to decide search direction [OK]

Common Mistakes:

• Not updating left/right correctly
• Confusing indices after rotation
• Returning wrong index or -1 incorrectly

4. Identify the bug in the following Java method for searching in a rotated sorted array:

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

medium

A. The loop condition should be 'left <= right' instead of 'left < right'.

B. The mid calculation is incorrect and may cause overflow.

C. The method should return void instead of int.

D. The array should be sorted before searching.

Solution

1. Step 1: Analyze loop condition

   The loop uses 'while (left < right)', which misses the case when left == right, possibly skipping the last element check.

2. Step 2: Correct loop condition for binary search

   Binary search requires 'while (left <= right)' to ensure all elements are checked, including when left equals right.

3. Final Answer:

   The loop condition should be 'left <= right' instead of 'left < right'. -> Option A

4. Quick Check:

   Loop must include equality to check all elements [OK]

Hint: Use 'left <= right' in binary search loops [OK]

Common Mistakes:

• Using 'left < right' and missing last element
• Incorrect mid calculation causing overflow
• Returning wrong type or ignoring array rotation

5. Given a rotated sorted array with possible duplicates, which modification is needed in the binary search algorithm to correctly find the target?

hard

A. Ignore duplicates and apply normal rotated binary search

B. Use linear search instead of binary search

C. Sort the array before searching

D. Skip duplicates by incrementing left when nums[left] == nums[mid] == nums[right]

Solution

1. Step 1: Understand duplicates effect on rotated binary search

   Duplicates can make it unclear which half is sorted because nums[left], nums[mid], and nums[right] may be equal.

2. Step 2: Modify search to handle duplicates

   When nums[left] == nums[mid] == nums[right], increment left by 1 to skip duplicates and reduce search space safely.

3. Final Answer:

   Skip duplicates by incrementing left when nums[left] == nums[mid] == nums[right] -> Option D

4. Quick Check:

   Skip duplicates to maintain binary search correctness [OK]

Hint: Skip duplicates when ends equal to avoid confusion [OK]

Common Mistakes:

• Ignoring duplicates causing infinite loops
• Switching to linear search unnecessarily
• Sorting array breaks problem constraints