Binary Search

Binary search is the classic "guess the number" strategy. If I pick a number between 1 and 100 and tell you higher or lower each guess, you never start at 1 — you start at 50, then halve the range every turn. After at most 7 guesses you have it. That is O(log n) in action.

The one prerequisite: the data must be sorted (or otherwise monotonic). Sorting buys you the ability to discard half the array with a single comparison — the whole trick.

The algorithm

Keep two bounds, lo and hi. Look at the middle. If it is the target, done. If the target is larger, it must be in the right half, so move lo past mid. Otherwise move hi before mid. Repeat until the bounds cross.

function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1)   // avoids overflow
    if (arr[mid] === target) return mid
    if (arr[mid] < target) lo = mid + 1
    else hi = mid - 1
  }
  return -1   // not found
}

The real skill: binary search on the answer

The deeper pattern is not "find x in an array" — it is "find the smallest/largest value that satisfies a monotonic condition." If a predicate flips from false to true exactly once as the value grows, you can binary-search the boundary even when there is no literal array to search.

function lowerBound(arr, target) {
  let lo = 0, hi = arr.length   // note: hi = length
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1)
    if (arr[mid] < target) lo = mid + 1
    else hi = mid
  }
  return lo   // insertion point
}

• Works only on monotonic data — sort first if needed (O(n log n)).
• Returns in O(log n) with O(1) extra space.
• Variants to know cold: lowerBound, upperBound, first/last occurrence, and search in a rotated array.