Suggest an edit

Improve this article

Refine the answer for “What is binary search?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

Binary search is an algorithm for searching sorted data that halves the range at each step and discards one half. Thanks to this it runs in O(log n) time and O(1) memory (in iterative form). It applies to arrays/intervals where monotonicity holds: all "less than the target" elements come before all "not less than the target" elements.

## Detailed answer

### When to use it

- The data is sorted (or the problem defines a monotonic predicate: as the index/parameter increases, the condition does not switch from true back to false).
- There is random access by index (array/string/numeric range). Binary search is inefficient on linked lists.
- You need fast search/insertion-position lookup in a large sorted array.

### How it works (the idea)

1. Choose the range bounds: lo and hi.
2. Find the middle, mid = lo + floor((hi - lo) / 2).
3. Compare arr[mid] with the target and discard a half: shift either lo or hi.
4. Repeat until the range becomes empty.

### Complexity

- Time: O(log n).
- Memory: O(1) for the iterative version; O(log n) for the recursive one, due to the call stack.

### Basic implementation (iterative, JS)

```js
function binarySearch(arr, x) {
  let lo = 0;
  let hi = arr.length - 1;

while (lo <= hi) {
    // A safe middle, without overflow and without a 32-bit shift
    const mid = lo + Math.floor((hi - lo) / 2);

if (arr[mid] === x) return mid;
    if (arr[mid] < x) lo = mid + 1;
    else hi = mid - 1;
  }

return -1; // not found
}

// Example
const a = [1, 3, 4, 7, 9, 12, 18];
console.log(binarySearch(a, 7)); // 3
console.log(binarySearch(a, 8)); // -1
```

In JavaScript, numbers are 64-bit floating point, so there is no classic overflow like in Java/C++. But bit shifts coerce to a 32-bit integer, which can be undesirable for very large indices, so use Math.floor((hi - lo) / 2).

### First/last position and insertion index

Often you need not "some" index of an equal element, but the left/right boundary or the insertion position.

```js
// lowerBound: the first position where the element is >= x (left boundary)
function lowerBound(arr, x) {
  let lo = 0, hi = arr.length; // half-open interval [lo, hi)
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] < x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

// upperBound: the first position where the element is > x (right boundary + 1)
function upperBound(arr, x) {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] <= x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

// Range of all occurrences of x
function searchRange(arr, x) {
  const first = lowerBound(arr, x);
  const lastExclusive = upperBound(arr, x);
  return first === lastExclusive ? [-1, -1] : [first, lastExclusive - 1];
}

// Example
const b = [1, 2, 2, 2, 3, 5];
console.log(lowerBound(b, 2)); // 1
console.log(upperBound(b, 2)); // 4
console.log(searchRange(b, 2)); // [1, 3]
console.log(lowerBound(b, 4)); // 5 - the insertion index for 4
```

### Predicate search (binary search on the answer)

If there is a monotonic predicate pred(i), you can find the minimum i for which pred(i) is true. This is useful for optimization problems over a parameter.

```js
function firstTrue(lo, hi, pred) {
  // Returns the minimum i from [lo, hi] where pred(i) === true,
  // or hi + 1 if there are no true values
  let ans = hi + 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (pred(mid)) {
      ans = mid;
      hi = mid - 1; // narrow to the right toward the first true
    } else {
      lo = mid + 1; // shift toward true
    }
  }
  return ans;
}

// Example: the minimum n for which n*n >= target
const target = 50;
const i = firstTrue(0, 100, (n) => n * n >= target);
console.log(i); // 8, since 7*7=49 < 50, 8*8=64 >= 50
```

### Invariants and common mistakes

- Bounds and half-open intervals: for finding an index it is convenient to use [lo, hi] with the loop condition lo <= hi; for lower/upperBound, the half-open interval [lo, hi) with the condition lo < hi.
- The middle: compute mid as lo + floor((hi - lo) / 2), to avoid overflow and keep making progress.
- Duplicates: the basic variant returns any matching index. For the first/last position, use lowerBound/upperBound.
- Avoid infinite loops: after a comparison, always exclude mid from the next range (lo = mid + 1 or hi = mid - 1 for the [lo, hi] variant).
- Comparator consistency: compare the same way the array was sorted (especially for locale-aware strings and custom comparators).
- Do not use it on unsorted data - you will get an incorrect result.

### When it is better not to use it

- Small arrays, where linear search is simpler and there is no meaningful time difference.
- No random access (stream/iterator/linked list).
- Searching by key in unsorted structures - use a Map/Set instead. Binary search is meant specifically for sorted sequences.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts889 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.