jsschools

Binary Search

Halves the search space each step by comparing the target with the middle element; requires a sorted array and runs in O(log n).

Spec ↗

Syntax

binarySearch(arr, target)

Parameters

NameTypeRequiredDescription
arr Array<number> Yes A sorted array of numbers to search.
target number Yes The value to locate.

Returns

number — Index of target, or -1 if not found.

Examples

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

const sorted = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
console.log(binarySearch(sorted, 23));
console.log(binarySearch(sorted, 10));
Output 
5
-1

// Lower-bound variant: first index where arr[i] >= target
function lowerBound(arr, target) {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

const nums = [1, 3, 3, 5, 7, 9];
console.log(lowerBound(nums, 3)); // first 3 is at index 1
console.log(lowerBound(nums, 4)); // would insert at index 3
Output 
1
3

Notes

| Case | Time | Space | |---------|----------|-------| | Best | O(1) | O(1) | | Average | O(log n) | O(1) | | Worst | O(log n) | O(1) | Classic pitfall: `(lo + hi) / 2` can overflow a 32-bit integer in some languages; use `lo + ((hi - lo) >> 1)` or `(lo + hi) >>> 1` in JS. Binary search has many variants: exact match, lower-bound (first ≥ target), upper-bound (first > target), and can be applied to any monotone predicate (see binary-on-answer). The array **must** be sorted; calling on unsorted data produces undefined results.

See also