0
lo
A sorted array rotated at an unknown pivot always has one sorted half — identify it first, then check if the target lies within it to halve the search space, achieving O(log n) even without knowing where the rotation is.
Given a sorted array of distinct integers rotated at some pivot (e.g. [4,5,6,7,0,1,2]), find the index of target in O(log n) time, or return -1 if it is not present. For example, nums=[4,5,6,7,0,1,2], target=0 → 4; target=3 → -1.
mid always leaves at least one half that is contiguously sorted. Compare nums[lo] with nums[mid]: if nums[lo] ≤ nums[mid], the left half is sorted; otherwise the right half is sorted. Once you know which half is sorted, a simple range check tells you whether target lives there — if yes, search that half; if no, search the other.lo=0, hi=n-1. Loop while lo ≤ hi.nums[mid] === target return mid.nums[lo] ≤ nums[mid] → left half is sorted; otherwise right half is sorted.< instead of ≤ when checking nums[lo] ≤ nums[mid]. When lo === mid (two-element window) you must treat the left half as sorted. The = is load-bearing.The rotation does not change the search space halving — we eliminate half the elements at every step just as in regular binary search. Space is O(1): only two pointers.
nums[lo] === nums[mid] forces a linear fallback) and Find Minimum in Rotated Sorted Array (find the pivot instead of a target).0 in rotated array [4, 5, 6, 7, 0, 1, 2]. Set lo=0, hi=6.function search(nums: number[], target: number): number {
let lo = 0;
let hi = nums.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (nums[mid] === target) return mid;
// Determine which half is sorted
if (nums[lo] <= nums[mid]) {
// Left half [lo..mid] is sorted
if (nums[lo] <= target && target < nums[mid]) {
hi = mid - 1; // target in left sorted half
} else {
lo = mid + 1; // target must be in right half
}
} else {
// Right half [mid..hi] is sorted
if (nums[mid] < target && target <= nums[hi]) {
lo = mid + 1; // target in right sorted half
} else {
hi = mid - 1; // target must be in left half
}
}
}
return -1;
}lo=0, hi=n-1, loop while the window is non-empty.nums[mid] is the target we are done. Always check this before the sorted-half logic.nums[lo] ≤ nums[mid] means the left half has no wraparound — it is fully ascending. The = is essential: when the window is two elements, lo === mid and we must count the left half as sorted.[nums[lo], nums[mid]). If yes, cut the right half away (hi = mid - 1); otherwise the target must be right of the pivot (lo = mid + 1).(nums[mid], nums[hi]]. If yes, advance lo = mid + 1; otherwise the target is in the left (possibly rotated) portion (hi = mid - 1).lo > hi; the target was never matched. Return -1.lo, mid, hi pointers.nums[lo] === nums[mid] === nums[hi] you cannot determine which half is sorted, so increment lo and decrement hi — worst case degrades to O(n).lo === mid would misclassify the left half as unsorted and may loop infinitely or miss the target.| "rotated sorted array, O(log n)" | sorted-half binary search |
| identify pivot or minimum in rotated array | nums[lo] ≤ nums[mid] check |
| standard binary search but array may wrap | range-check the sorted half first |
| LC 81 (with duplicates) | same pattern + lo++/hi-- fallback for equals |
function search(nums: number[], target: number): number {
let lo = 0, hi = nums.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (nums[mid] === target) return mid;
if (nums[lo] <= nums[mid]) { // left half sorted
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // right half sorted
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}nums[lo] ≤ nums[mid] the left half is sorted; otherwise the right half is sorted.nums=[4,5,6,7,0,1,2], target=0, which half is sorted on the first iteration (lo=0, mid=3, hi=6)?hi = mid - 1?nums[lo] ≤ nums[mid] (with =) used instead of strict <?nums=[1], target=0. What does the algorithm return?