This site uses one functional cookie to keep feature rollouts consistent for you. Nothing is set until you choose. See the privacy notice.
Cut the search space in half every step. Not just for "find X in a sorted array" — also for "find the smallest or largest value where some condition flips."
Pick a target. Each step computes the midpoint, compares, and throws away half the remaining elements.
Find 11 in the sorted array. left=0, right=9.
Binary search works whenever you have a monotonic predicate — a condition that's false for a while, then true forever (or vice versa). The search finds the boundary.
The sorted-array version is just a special case: the predicate is "is this element ≥ the target?" Most binary search interview problems are really about finding this boundary.
"Minimum ship capacity to deliver all packages in D days." Don't search an array — binary search on the answer itself. For each candidate capacity, check if it works.
Ship [3, 2, 5, 1, 4] in 2 days. Capacity range: 5 to 15.
Classic — find target in sorted array
function binarySearch(arr: number[], target: number) { let left = 0, right = arr.length - 1 while (left <= right) { const mid = Math.floor((left + right) / 2) if (arr[mid] === target) return mid if (arr[mid] < target) left = mid + 1 else right = mid - 1 } return -1 }
Search the answer — find boundary of a predicate
function searchAnswer(lo: number, hi: number) { while (lo < hi) { const mid = Math.floor((lo + hi) / 2) if (predicate(mid)) hi = mid else lo = mid + 1 } return lo // smallest true }
O(log n) time