The problem. Given an array of integers nums sorted in ascending order with no duplicates, and an integer target, return the index of target, or -1 if it isn't there. Your algorithm must run in O(log n) time.
nums = [-1, 0, 3, 5, 9, 12], target = 9 -> 4
nums = [-1, 0, 3, 5, 9, 12], target = 2 -> -1
nums = [5], target = 5 -> 0The problems in this chapter are binary search with one small twist each: an exact match here, an insert position, a hidden API instead of an array, and a search over numbers instead of indexes. Get the basic loop right — the invariant that the target, if present, is always inside low..high — and each twist is a one-line change.
function search(nums, target) { for (let i = 0; i < nums.length; i++) { if (nums[i] === target) return i; } return -1;}Time O(n), space O(1). Correct, but it ignores that the array is sorted — and the problem demands O(log n).
Each check rules out half of what's left: the target is always inside low..high.
function binarySearch(nums, target) { let low = 0; let high = nums.length - 1; while (low <= high) { const mid = low + Math.floor((high - low) / 2); if (nums[mid] === target) return mid; if (nums[mid] < target) low = mid + 1; // the target is to the right else high = mid - 1; // the target is to the left } return -1;}Time O(log n), space O(1). low <= high keeps checking until the range is empty, and mid ± 1 drops the value just checked so the range always shrinks.
Find the first index whose value is at least the target with the lower-bound template, then check whether it holds the target. It's just as fast, and with duplicates it would return the first match, which plain binary search doesn't promise.
function search(nums, target) { let low = 0, high = nums.length; while (low < high) { const mid = low + Math.floor((high - low) / 2); if (nums[mid] < target) low = mid + 1; else high = mid; } return low < nums.length && nums[low] === target ? low : -1; // the first value >= target: is it the target?}Time O(log n), space O(1).
[5] with target 5 and with target 3.mid equals low; a wrong update loops forever.guess(num) replaces the comparison.high until it passes the target, then binary search: still O(log n).