Rotated Sorted Arrays: Binary Search Modification

1. What is a Rotated Sorted Array?

Imagine you have a perfectly sorted array, like [0, 1, 2, 4, 5, 6, 7]. If you "rotate" it at a pivot point, you might get an array like [4, 5, 6, 7, 0, 1, 2].

A standard binary search won't work here. Why? Because the core assumption of binary search—if target < arr[mid], then the target must be in the left half—is no longer true. In our example [4, 5, 6, 7, 0, 1, 2], the midpoint is 7. If our target is 0, it's less than 7, but it lies in the right half of the array!

To understand the problem setup more formally, please watch the first few minutes of this video.

2. The Modified Binary Search Algorithm

Since a brute-force linear search (O(n)) is too slow for interview standards, we need a solution with O(log n) time complexity. This points us back to binary search. The key is to modify it.

The most crucial observation is this: At any given mid point, one half of the array (from low to mid, or from mid to high) will always be perfectly sorted.

Our strategy will be:

1. Find the mid element.
2. Identify which of the two halves is sorted.
3. Check if our target lies within the range of that sorted half.
   • If yes, we search within that sorted half by moving our low or high pointer.
   • If no, the target must be in the other, unsorted half, so we search there instead.

This logic ensures that with every step, we correctly discard half of the remaining elements.

Let's watch a detailed explanation of how to implement this logic.

The Logic in a Nutshell:

Let's say you're inside your while (low <= high) loop:

1. Calculate mid. If nums[mid] == target, you've found it. Return mid.
2. Check if the left half [low...mid] is sorted. This is true if nums[low] <= nums[mid].
   • If it is sorted, ask: Is the target within this sorted range? (i.e., nums[low] <= target && target < nums[mid]).
     • If yes, the target must be in the left half. So, high = mid - 1.
     • If no, the target must be in the right half. So, low = mid + 1.
3. If the left half is not sorted, then the right half [mid...high] must be sorted.
   • Ask: Is the target within this sorted right half? (i.e., nums[mid] < target && target <= nums[high]).
     • If yes, the target must be in the right half. So, low = mid + 1.
     • If no, the target must be in the left half. So, high = mid - 1.

3. Implementation in Java

Now that you understand the logic, let's look at how it translates into a clean, iterative Java implementation. This is the kind of code you would be expected to write in an interview setting.

The code you just reviewed has a time complexity of O(log n) because it halves the search space at each iteration. The space complexity is O(1) because we are only using a few variables to store pointers (low, high, mid) without using any extra data structures that scale with the input size.

4. What About Duplicates?

A common follow-up question in interviews is: "How would your algorithm change if the array could contain duplicates?"

Consider an array like [3, 1, 2, 3, 3, 3, 3].
If low=0 (nums[low]=3) and high=6 (nums[high]=3), then mid=3 (nums[mid]=3).
In this case, nums[low] == nums[mid] == nums[high]. We can't determine which side is sorted!

When this specific condition occurs, we can't make an intelligent decision to eliminate half the array. The safe fallback is to shrink the search space by one from both ends and try again.

// Inside the while loop, if this edge case occurs:
if (nums[low] == nums[mid] && nums[mid] == nums[high]) {
    low++;
    high--;
    continue; // Continue to the next iteration
}

// ... rest of the logic

This handles the ambiguity. However, be aware that in the worst-case scenario (e.g., an array of all the same element except one), this fix degrades the time complexity to O(n) because you might have to shrink the array one element at a time. It's important to mention this trade-off in an interview.

Conclusion

Congratulations! You have now mastered another crucial variation of binary search. This problem is a testament to the idea that understanding the invariants (the rules that always hold true, like "one half is always sorted") is key to adapting algorithms to new challenges.

Key Takeaways:

• A rotated sorted array consists of two individually sorted segments.
• Standard binary search fails because the global monotonic property is broken.
• A modified binary search can achieve O(log n) time complexity by identifying the sorted half at each step and checking if the target lies within it.
• The presence of duplicates can create ambiguity, potentially degrading the worst-case performance to O(n) if not handled carefully.

Preview of the next lesson:
We'll be shifting gears from searching algorithms to a powerful array manipulation technique. In the next lesson, you will learn to apply prefix/suffix sum techniques to solve range query problems, which is an essential tool for efficiently calculating sums over various subarrays.