33. Search in Rotated Sorted Array - Detailed Explanation

Problem Statement

Given an integer array nums that was originally sorted in ascending order and then rotated at some unknown pivot, find the index of a given target value in the array. If the target is not present, return -1. The array has no duplicate values, and an efficient solution with O(log n) time complexity is required.

What is a rotated sorted array?

It’s an array that starts sorted but then is “rotated” – a tail segment is cut off and placed in front. For example, the sorted array [0,1,2,4,5,6,7] might be rotated at index 3 to become [4,5,6,7,0,1,2]. Here, the part [4,5,6,7] (from index 0 to 3) was originally the end of the sorted array, and [0,1,2] (from index 4 to 6) was the start of the sorted array.

Goal: After such a rotation, determine the index of target in nums. Return -1 if the target is not found.

Examples:

• Example 1: Input: nums = [4,5,6,7,0,1,2], target = 0 – Here the array [4,5,6,7,0,1,2] is a rotated version of [0,1,2,4,5,6,7]. The target value 0 is present at index 4, so the output is 4.

• Example 2: Input: nums = [4,5,6,7,0,1,2], target = 3 – The target 3 is not in the array, so the output is -1.

• Example 3: Input: nums = [1], target = 0 – With only one element in the array (which is 1), the target 0 is not present, so the output is -1.

Constraints: Typical constraints for this problem are:

• 1 <= nums.length <= 5000 (the array has at least 1 element and at most 5000 elements).
• -10^4 <= nums[i] <= 10^4 for each element, and all values in nums are unique.
• nums is sorted in ascending order initially, then possibly rotated at some pivot.
• -10^4 <= target <= 10^4 (the target value range).
• The solution must run in O(log n) time, hinting that a binary search approach is expected.

Hints

• Two Sorted Halves: A key insight is that a rotated sorted array can be thought of as two sorted subarrays joined together. If you split the array at the rotation point, each part is individually sorted. Even if you don’t know the rotation point, when you pick a middle index, at least one side of the array (left or right) will be in sorted order. This is because the rotation does not disturb the sorted order within each half. Exploiting this property is crucial.

• Modified Binary Search: You can adapt binary search to work on the rotated array. Compare the middle element with the target and determine which half is sorted. If the target lies within the sorted half’s range, discard the other half; otherwise, discard the sorted half. This way, you reduce the search space by half each time, maintaining O(log n) complexity.

• Finding the Pivot (Alternative Hint): Another approach is to first find the “pivot” point where the array was rotated (for example, the index of the smallest element or largest element). Once you know the pivot, you effectively know the sorted subarrays. You can then perform a standard binary search in the relevant half. This two-step method (find pivot, then binary search) also achieves O(log n) time in total.

• Edge Scenarios: Consider edge cases such as when the array is not rotated at all (already sorted), or rotated at the last element, as well as very small arrays (one or two elements). A correct approach should handle these seamlessly.

Approaches to Solve the Problem

Brute Force Solution (Linear Search)

A straightforward solution is to simply scan through the array and check each element against the target. This requires no special insight:

1. Traverse the array: Start from index 0 and move rightwards up to n-1. Compare each element with the target.

2. Check for target: If an element equals the target, return that index.

3. If end reached: If the entire array is scanned without finding the target, return -1.

This approach will definitely find the target if it exists. However, its time complexity is O(n) because in the worst case you might check every element. For example, if nums = [6,7,0,1,2,4,5] and target = 5, a linear search would examine each element until the last index. While O(n) is acceptable for small arrays, it does not meet the O(log n) requirement for larger inputs and is not efficient if nums is very large.

When to use: Generally, the brute force method is used as a conceptual baseline or when n is very small. In an interview or competitive programming context, it’s usually intended that you find a faster solution.

Optimized Binary Search Approach

The optimal solution uses a modified binary search to achieve O(log n) time. The idea is to leverage the fact that although the array as a whole is not sorted, each of the two halves (around the rotation pivot) is sorted. By comparing the middle element with the ends, we can decide which half is sorted and then determine where to search next.

How it works:

1. Initialize Pointers: Set two pointers, l = 0 (left start) and r = n-1 (right end), at the boundaries of the array. We will maintain a search window between l and r.

2. Binary Search Loop: Repeat the following until the search window is empty:

   • Compute mid = (l + r) // 2, the index of the middle element in the current window.
   • If nums[mid] is exactly the target, return mid (found the target).
   • Otherwise, determine which side of mid is sorted:
     • Left side sorted: If nums[l] <= nums[mid], then the left portion from index l to mid is sorted in ascending order.
       • If the target lies between nums[l] and nums[mid] (inclusive), then the target must be in this sorted left half. So, set r = mid - 1 to discard the right half.
       • Otherwise, the target must be in the other half, so set l = mid + 1 to discard the left half.
     • Right side sorted: Else (if the left side isn’t sorted, then the right side from mid to r must be sorted ), check the right portion.
       • If the target lies between nums[mid] and nums[r] (inclusive of nums[r]), then move search to the sorted right half by setting l = mid + 1.
       • Otherwise, the target is in the left half, so set r = mid - 1.
   • Continue this process, narrowing down the search window by half each time.

3. Not Found: If the loop ends (i.e., l becomes greater than r) without finding the target, return -1 (target isn’t in the array).

This approach discards half of the array in each iteration by determining which side is sorted and whether the target is on that side. As a result, the time complexity is O(log n). The algorithm hinges on the fact that one of the two halves is always sorted in a rotated array. By using the sorted half to guide the search, we efficiently hone in on the target.

Illustration of the Binary Search Approach: Suppose nums = [4,5,6,7,0,1,2] and target = 0. Initially, l=0, r=6. We then follow these steps:

• Step 1: l=0, r=6. Compute mid = (0+6)//2 = 3.

  • nums[mid] = 7. This is not the target.
  • Check which half is sorted: Compare nums[l] and nums[mid] -> nums[0]=4 and nums[3]=7. Since 4 <= 7, the left half [4,5,6,7] is sorted.
  • Determine target’s half: Is target=0 in the range [nums[l]=4 ... nums[mid]=7]? No, 0 is smaller than 4. This means the target must be in the other half (the right side) which is [0,1,2].
  • Discard left half: set l = mid + 1 = 4. Now the search is restricted to indices 4..6.

• Step 2: Now l=4, r=6. Compute mid = (4+6)//2 = 5.

  • nums[mid] = 1. Not the target.
  • Check sorted half: Compare nums[l] and nums[mid] -> nums[4]=0 and nums[5]=1. 0 <= 1, so the left half from index 4 to 5 (which is [0,1]) is sorted.
  • Is target=0 in range [nums[l]=0 ... nums[mid]=1]? Yes – 0 is between 0 and 1. So the target lies in this left half.
  • Discard right half: set r = mid - 1 = 4. Now the search is restricted to index 4..4 (just one element).

• Step 3: Now l=4, r=4. Compute mid = (4+4)//2 = 4.

  • nums[mid] = 0, which matches the target! We return index 4.

At this point we found the target. If instead the target was not in the array, eventually the l and r pointers would cross and the loop would end, resulting in -1. In this example, we found 0 in three steps by discarding half of the array at each step, rather than checking each element.

Alternative Approaches

While the one-pass binary search is the most common solution, there are alternative methods to solve the problem:

• Find the Pivot, Then Binary Search: An alternate strategy is to first find the index where the array is rotated (often called the “pivot” – in a rotated array, this could be the index of the smallest element or the point where the order breaks). Once you have the pivot:

  1. You know the array is sorted from 0 to pivot-1 and from pivot to n-1. Decide which part the target would lie in by comparing with the array endpoints.
  2. Perform a standard binary search on the appropriate half.

  For example, consider nums = [4,5,6,7,0,1,2] again. The smallest element is 0 at index 4, so you could determine the pivot as 4 (some implementations might find pivot as index of largest element which would be 3 in this case – both interpretations work with slight adjustments). Since target = 0 is equal to nums[4], you’d immediately return 4. If instead the target was, say, 5, you see that 5 >= nums[0] (first element) so it must lie in the first half (indexes 0–3). You would then binary search [4,5,6,7] for 5. This two-step method – find pivot, then search – also runs in O(log n) time. It’s a bit more verbose to implement because you handle two binary searches (one to find pivot, one to find target) but conceptually straightforward.

• Recursive Binary Search: You can implement the binary search approach recursively as well. The logic remains the same (check mid, decide which half to recurse into) but using recursion instead of a loop.

• Library Functions / Built-in Search: In a real scenario, you might be tempted to rotate the array back to sorted order or use built-in search functions. For example, if you knew the pivot, you could physically rotate the array back (which is O(n)) and then do a normal binary search. However, this would violate the O(log n) requirement and use extra memory, so it’s not recommended in an interview setting. It’s better to adapt binary search as described above.

Each of these approaches must ultimately utilize the binary search logic to meet the efficiency requirement. The primary differences lie in whether you explicitly find the rotation point first or handle the rotation implicitly during the search.

Step-by-Step Walkthrough with Visual Example

Let’s walk through a visual example to solidify the concept. Consider the array nums = [15, 18, 2, 3, 6, 12] and suppose we want to search for target = 6. This array is a rotated version of [2, 3, 6, 12, 15, 18] (rotated at the index where value 2 starts). We will trace the binary search approach step by step:

Visualizing the binary search on a rotated array. In the diagram, the blue line represents the array values in sorted order, and the green/red shading shows which side is currently sorted (green for sorted portion, red for unsorted). The pointers l, m (mid), and r move based on comparisons. The top-right diagrams indicate checking which side of the array is sorted (left diagram shows left side sorted, right diagram shows right side sorted). The bottom diagrams illustrate how we move the l and r pointers in different scenarios: if the target is greater than nums[m] or less than nums[l] (bottom left), we move l to m+1; if the target is less than nums[m] or greater than nums[r] (bottom right), we move r to m-1. This process continues until we find the target or the pointers cross. In our example array, initially the left side is sorted, and we adjust the pointers according to the rules until the target 6 is found.

Now, using the same example [15, 18, 2, 3, 6, 12] step-by-step:

• Initial state: l = 0, r = 5 (array indices 0 to 5). The array looks like:

  Index:  0   1   2   3   4   5
  Value: [15, 18,  2,  3,  6, 12]
  

  The array is clearly rotated (the smallest value 2 is in the middle). We compare middle:

  • Calculate mid = (0+5)//2 = 2. So mid index is 2, and nums[mid] = 2.
  • This is not our target (6), so decide which half is sorted.
  • Compare nums[l] to nums[mid]: nums[0] = 15, nums[2] = 2. Since 15 > 2, the left side is not sorted. Therefore, the right side (from mid to r) must be sorted.
  • Indeed, the subarray [2, 3, 6, 12] (indices 2 to 5) is sorted in ascending order.
  • Now, is the target 6 in this sorted right half’s range? The range of values in indices [2..5] is 2 to 12. Yes, 6 lies between 2 and 12.
  • Because the target is in the sorted half, we keep that half and discard the other. Here, the sorted half is the right half, so we set l = mid + 1 = 3 to focus on indices 3..5 (we know index 2 is not the target and everything left of it can be ignored).

• Next iteration: Now l = 3, r = 5. New range is indices [3..5]:

  Index:  3   4   5
  Value: [ 3,  6, 12]
  

  Calculate mid = (3+5)//2 = 4. nums[mid] = 6. This matches our target!

  • We have found the target at index 4. We can return 4.

We found the target in two steps. If the target were not present, we would continue the process until l > r. Each decision discards half of the remaining elements, which is why the algorithm is efficient.

If you trace another scenario (say searching for a value not in the array, or searching in a non-rotated sorted array), you’ll see the algorithm gracefully handles those as well:

• If the array wasn’t rotated at all (fully sorted), the check would always go into one branch (say, the left-side-sorted branch) and effectively perform a normal binary search.
• If the target is not present, eventually the l and r pointers cross, and we return -1.
• If the array has just one element, the algorithm will check mid (which is the only element) and either find the target or end immediately.

By following the pointers and conditions carefully, you can hand-simulate the algorithm for various cases to build intuition.

Code Implementations

Python Solution