Binary Search on Rotated Arrays and Other Tricky Variants

Standard binary search fails the moment an array is rotated, not because the logic is wrong, but because you are looking at both halves with the assumption that the entire range is sorted. To fix this, you must identify which half remains strictly ordered, check if your target falls inside those clean boundaries, and discard the chaotic side.

Search in a Rotated Sorted Array

Take arr = [4, 5, 6, 7, 0, 1, 2] and search for 0. If you compute mid = 3 pointing to 7, the left half [4, 5, 6, 7] is sorted, but the right half [0, 1, 2] is also sorted.

One half is always sorted in a single rotation, and the other half contains the pivot point. You check arr[low] <= arr[mid] to confirm the left side is normal. If it is, and your target sits between arr[low] and arr[mid], move your high pointer to mid - 1. Otherwise, search the right half.

Find Minimum in Rotated Array

When an array like [5, 6, 1, 2, 3, 4] rotates, the minimum element breaks the sorted property. Compare arr[mid] directly against arr[high].

If arr[mid] > arr[high], the minimum hides in the right half, so set low = mid + 1. If arr[mid] <= arr[high], the minimum is at mid or to its left, so set high = mid. You do not need to check the left boundary against mid. The right boundary gives you the slope you need to determine where the drop occurs.

First and Last Occurrence

Finding duplicates with standard binary search leaves you guessing which index you landed on. When arr[mid] == target, do not return immediately.

If you want the first occurrence, shift high = mid - 1 to keep searching left. If you want the last occurrence, shift low = mid + 1 to keep searching right. Store the valid index in a separate variable every time you match the target.

Peak Element

A peak element is an item greater than or equal to its neighbors, such as 3 in [1, 2, 3, 1]. If arr[mid] < arr[mid + 1], a peak must exist on the right side because values are climbing.

Move low = mid + 1. If arr[mid] > arr[mid + 1], the peak is at mid or on the left side, so move high = mid. You do not need bounds checking for the ends if you handle array sizes of one or two separately or let index comparisons naturally constrain your pointers.

Decision Rule Checklist

1. Identify which half of mid is normally sorted by comparing endpoints.
2. Check if the target lives inside the sorted half's numeric range.
3. Drop the half that fails the range test or lacks the pivot.
4. For duplicates or boundaries, continue searching past the match instead of stopping.

Practice these patterns on DSA Tracker before your next coding test. Pick one rotated search problem and trace the pointers on paper for an input with negative numbers.

Keep going with the step-by-step visualizer and practice problems.

Further reading: Binary search on Wikipedia.