A complete visual walkthrough of the modified binary search — understanding which half is sorted and where the target hides.
The naive approach ignores the sorted structure entirely: just scan every element until you find the target.
for (int i = 0; i < nums.length; i++) { if (nums[i] == target) return i; } return -1;
This is O(n) — it works but ignores the fact that the array is nearly sorted. The problem explicitly requires O(log n), which means binary search.
Key question: Standard binary search needs a fully sorted array. A rotated array has a "break point." How can we still use binary search? The trick is recognizing that at least one half is always sorted.
When you pick the midpoint of a rotated sorted array, the rotation break can only be in one half. The other half is guaranteed to be perfectly sorted.
Array [4, 5, 6, 7, 0, 1, 2] — rotated at index 4. The values form a "broken staircase":
The left segment [4,5,6,7] is sorted. The right segment [0,1,2] is also sorted. The break is between them.
[nums[lo], nums[mid]). If yes, search left. Otherwise search right.(nums[mid], nums[hi]]. If yes, search right. Otherwise search left.Why does this work? In the sorted half, we can definitively say whether the target is there (it must be within its range). If the target is not in the sorted half, it must be in the other half — the one containing the rotation break.
Let's trace nums = [4,5,6,7,0,1,2], target = 0 step by step.
| Iter | lo | hi | mid | nums[mid] | Sorted Half | Action |
|---|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 7 | Left [4,5,6,7] | target=0 not in [4,7] → lo = 4 |
| 2 | 4 | 6 | 5 | 1 | Right [1,2] | target=0 not in (1,2] → hi = 4 |
| 3 | 4 | 4 | 4 | 0 | — | Found! return 4 |
Visual state at each iteration:
nums[lo] <= nums[mid] check handles both correctly.class Solution { public int search(int[] nums, int target) { int lo = 0, hi = nums.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // Found the target if (nums[mid] == target) return mid; if (nums[lo] <= nums[mid]) { // Left half [lo..mid] is sorted if (target >= nums[lo] && target < nums[mid]) hi = mid - 1; // target is in sorted left half else lo = mid + 1; // target is in right half } else { // Right half [mid..hi] is sorted if (target > nums[mid] && target <= nums[hi]) lo = mid + 1; // target is in sorted right half else hi = mid - 1; // target is in left half } } return -1; // target not found } }
Enter a rotated sorted array and a target value. Step through to see which half is identified as sorted and how pointers move.
Each iteration halves the search space, just like standard binary search. We use only a constant number of variables — no extra data structures needed.
The rotation does not hurt us. Even though the array is not fully sorted, the property that one half is always sorted gives us enough information to decide which half to discard. We get the same O(log n) guarantee as normal binary search.