Searching in Rotated Sorted Arrays

1. The Brute-Force Approach: Linear Scan

As always, let's begin with the most direct solution. Since we need to find an element, we can simply iterate through the array from the beginning and check each element against our target. If we find it, we return its index. If we reach the end of the array without a match, we return -1.

This linear search has a time complexity of $O(n)$. While correct, the problem's structure—a "rotated sorted" array—hints that we can do much better. The presence of sorted segments is a strong signal to apply a logarithmic-time approach like binary search.

2. Optimal Approach: Modified Binary Search for Unique Elements

A standard binary search won't work directly because the array isn't sorted end-to-end. If we pick a mid element, we can't reliably say whether the target is in the left or right half based on a simple comparison like target < nums[mid].

The key insight is that in any given range [low, high], at least one of the two halves—[low, mid] or [mid, high]—must be sorted. Our strategy will be to identify which half is sorted and then use that information to intelligently eliminate one half of the search space.

The following video provides an exceptional explanation of this core idea.

The Algorithm

Here is the step-by-step breakdown of the modified binary search:

1. Initialize low = 0 and high = n - 1.
2. While low <= high, calculate mid.
3. If nums[mid] == target, we found it. Return mid.
4. Identify the sorted half:
   • Check if the left half is sorted: if (nums[low] <= nums[mid]).
   • If it is, check if the target lies within the bounds of this sorted half (nums[low] <= target && target < nums[mid]).
     • If yes, the target must be in the left half, so eliminate the right: high = mid - 1.
     • If no, the target must be in the unsorted right half: low = mid + 1.
   • Else, the right half must be sorted (nums[mid] <= nums[high]).
   • Check if the target lies within the bounds of this sorted right half (nums[mid] < target && target <= nums[high]).
     • If yes, the target must be here, so eliminate the left: low = mid + 1.
     • If no, the target must be in the unsorted left half: high = mid - 1.
5. If the loop finishes, the target was not found. Return -1.

For a clean implementation and formal algorithm description, the takeuforward article is an excellent reference.

3. The Plot Twist: Handling Duplicates

The previous solution works perfectly for arrays with unique elements. But what if the array contains duplicates? This introduces a subtle but critical edge case that can break our logic.

Consider an array like [3, 1, 3, 3, 3]. If low is at index 0, high is at index 4, then mid will be at index 2. Here, nums[low] = 3, nums[mid] = 3, and nums[high] = 3. In this scenario, nums[low] == nums[mid], which would normally imply the left half is sorted. However, that's not true ([3, 1, 3] is not sorted). Similarly, nums[mid] == nums[high] doesn't guarantee the right half is sorted.

When nums[low] == nums[mid] == nums[high], we are unable to determine which half is sorted.

The Solution: Shrink and Conquer

How do we handle this ambiguous case? The solution is surprisingly simple. When we can't decide which half to eliminate, we can't make a logarithmic leap. Instead, we take a small, safe step: we shrink our search space by just one element from each end.

The Modified Algorithm (with Duplicates):

1. Add a check at the beginning of your loop:
   if (nums[low] == nums[mid] && nums[mid] == nums[high])
   • If this is true, we simply shrink the bounds: low++, high--, and continue to the next iteration.
2. The rest of the logic for identifying the sorted half and eliminating portions of the array remains exactly the same as in the unique elements case.

This small addition makes our algorithm robust enough to handle duplicates.

Complexity with Duplicates

This change has a significant impact on the worst-case time complexity.

• Average Case: The algorithm still performs in $O(\log n)$ time.
• Worst Case: In a scenario with many duplicates, such as [3, 3, 3, 3, 1, 3, 3] where you're searching for 1, the algorithm might have to shrink the search space linearly many times. This degrades the worst-case time complexity to $O(n)$. The space complexity remains $O(1)$.

The following article provides a superb, in-depth explanation, a full Java implementation, and a discussion of common pitfalls to avoid—essential for interview preparation.

Conclusion

Today, we've extended our binary search toolkit to handle a non-trivial variation: searching in a rotated sorted array. We saw how a key observation—that one half must always be sorted—allows us to adapt binary search for an efficient solution.

Key Takeaways:

• Core Strategy: In a rotated sorted array, always use binary search to identify the sorted half first ([low, mid] or [mid, high]). Then, check if your target lies in that sorted half to decide which part of the array to eliminate.
• Unique Elements: This strategy guarantees an $O(\log n)$ solution.
• Duplicate Elements: An ambiguous case arises when nums[low], nums[mid], and nums[high] are all equal. We handle this by safely shrinking the search space (low++, high--), which leads to an $O(n)$ worst-case time complexity but preserves the $O(\log n)$ average case.

In our next lesson, we will pivot from searching algorithms to a different application of the divide-and-conquer paradigm. We will explore how to adapt the logic of Merge Sort to solve the "Count Inversions" problem, a challenge that requires thinking about element pairs rather than just single targets.