ASAPUtils
The signal
The input is sorted, the task is exact lookup, and O(log n) is required. Sorted order turns one comparison into proof about an entire half.
The invariant
If the target exists, its index is inside the inclusive interval
[l, r].
Start with the full array. After checking mid:
nums[mid] < target→ mid and everything left are too small.nums[mid] > target→ mid and everything right are too large.- equal → found.
Every update preserves the invariant and removes mid, guaranteeing progress.
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[mid] < target) 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[mid] < target) l = mid + 1;
else r = mid - 1;
}
return -1;
}
Why l <= r
Both ends are candidates. When l === r, one value remains and must be checked. The search is empty
only after the pointers cross. This matches the mid ± 1 updates; changing one without the other
changes the interval contract.
Complexity
O(log n) time and O(1) extra space. A recursive version uses O(log n) call-stack space without adding any clarity here.
Traps
- Writing
l < rand never inspecting the final candidate. - Updating
l = midorr = mid, which can repeat the same midpoint forever. - Returning
midafter the loop; a failed search returns −1. - Sorting the input inside the function. The problem already guarantees order, and sorting would change the required complexity and original indices.
Blank re-solve prompt
Search an ascending array in O(log n). State the exact interval represented by l and r before writing the loop condition.