Introduction

Searching a rotated sorted array in O(log n) time is a classic binary-search variant. The trick is that although the whole array is not globally sorted, at least one half of the current search interval is always sorted.

Use Binary Search with a Sorted-Half Check

Consider a rotated array such as [4, 5, 6, 7, 0, 1, 2]. At any midpoint, either the left half or the right half is still ordered normally. Once you know which half is sorted, you can decide whether the target belongs there.

1def search_rotated(nums, target):
2    left, right = 0, len(nums) - 1
3
4    while left <= right:
5        mid = left + (right - left) // 2
6
7        if nums[mid] == target:
8            return mid
9
10        if nums[left] <= nums[mid]:
11            if nums[left] <= target < nums[mid]:
12                right = mid - 1
13            else:
14                left = mid + 1
15        else:
16            if nums[mid] < target <= nums[right]:
17                left = mid + 1
18            else:
19                right = mid - 1
20
21    return -1
22
23
24print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))
25print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3))

This keeps the search logarithmic because each step discards half of the remaining range.

Why the Algorithm Works

In a rotated sorted array without duplicates, the pivot splits the data into two ascending segments. For any interval left..right, the midpoint must sit in one of those segments. That means one of the following is true:

• 'nums[left] <= nums[mid], so the left side is sorted'
• otherwise the right side is sorted

Once you identify the sorted half, checking whether the target falls inside its bounds tells you which side can be discarded safely. That is the same elimination principle that makes ordinary binary search efficient.

The iterative version also keeps space complexity at O(1) because it stores only index boundaries. A recursive version is logically equivalent, but it adds call-stack overhead without improving the time complexity.

Handle Duplicates as a Separate Variant

If duplicates are allowed, the sorted-half test can become ambiguous when nums[left] == nums[mid] == nums[right]. In that case, shrink the boundaries cautiously.

1def search_rotated_with_duplicates(nums, target):
2    left, right = 0, len(nums) - 1
3
4    while left <= right:
5        mid = (left + right) // 2
6
7        if nums[mid] == target:
8            return True
9
10        if nums[left] == nums[mid] == nums[right]:
11            left += 1
12            right -= 1
13            continue
14
15        if nums[left] <= nums[mid]:
16            if nums[left] <= target < nums[mid]:
17                right = mid - 1
18            else:
19                left = mid + 1
20        else:
21            if nums[mid] < target <= nums[right]:
22                left = mid + 1
23            else:
24                right = mid - 1
25
26    return False

This works, but the worst case can degrade toward linear time because duplicates can hide the ordering information.

Common Pitfalls

The biggest mistake is using ordinary binary search without checking which half is sorted. Rotation breaks the assumption that the entire interval is globally ordered.

Another common issue is getting the comparison bounds slightly wrong, especially around <= versus <. Those off-by-one mistakes often fail only on pivot-adjacent targets.

People also forget to test edge cases such as:

• single-element arrays
• arrays that were not rotated at all
• targets at the pivot
• targets that are absent

Finally, if the problem statement allows duplicates, do not assume the no-duplicates version still guarantees O(log n) in every case.

Summary

• This problem is solved with a modified binary search.
• At each step, one half of the interval is still sorted.
• Use the sorted half to decide whether to keep the left side or the right side.
• The no-duplicates version runs in O(log n).
• With duplicates, the logic becomes more ambiguous and can degrade toward linear time.