ASAPUtils
The signal
Ordinary binary search cannot compare only nums[mid] with target because global order has one
break. But rotation preserves enough structure: one side of mid is always normally sorted.
The decision tree
- If
nums[mid] === target, return. - If
nums[l] <= nums[mid], the left half is sorted.- If
nums[l] <= target < nums[mid], keep left. - Otherwise keep right.
- If
- Else the right half is sorted.
- If
nums[mid] < target <= nums[r], keep right. - Otherwise keep left.
- If
Notice which comparisons are inclusive: endpoint values remain candidates; mid was already checked.
Optimal solution
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) return mid;
if (nums[l] <= nums[mid]) {
if (nums[l] <= target && target < nums[mid]) r = mid - 1;
else l = mid + 1;
} else {
if (nums[mid] < target && target <= nums[r]) l = mid + 1;
else r = mid - 1;
}
}
return -1;
}
function search(nums, target) {
let l = 0, r = nums.length - 1;
while (l <= r) {
const mid = l + Math.floor((r - l) / 2);
if (nums[mid] === target) return mid;
if (nums[l] <= nums[mid]) {
if (nums[l] <= target && target < nums[mid]) r = mid - 1;
else l = mid + 1;
} else {
if (nums[mid] < target && target <= nums[r]) l = mid + 1;
else r = mid - 1;
}
}
return -1;
}
Why it stays logarithmic
Every iteration identifies one sorted half and discards one half. Rotation changes the comparison logic, not the shrink rate. Unique values are important; duplicates can make the sorted-half test ambiguous.
Complexity
O(log n) time, O(1) extra space.
Traps
- Trying to find the pivot first, then doing another search. Valid but more code and more boundaries.
- Checking target range before proving that half is sorted.
- Getting the endpoint inequalities wrong and dropping a target at
lorr. - Ignoring duplicates in a variant that allows them.
Blank re-solve prompt
Search a unique rotated array in one binary-search loop. Say “which half is sorted?” before every target comparison.