Suggest an edit

Improve this article

Refine the answer for “What is the complexity of 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

- Time: O(log n) on average and in the worst case; best case is O(1).
- Memory: O(1) for the iterative implementation; O(log n) for the recursive one (due to the call stack).
- Conditions: the data must be sorted; random access is required (array/dynamic array).

## In detail

### Idea of the algorithm

At each step, binary search compares the target element with the middle of the sorted range and discards half of the options, continuing in the remaining half.

### Time asymptotics

- Worst and average case: O(log n). The number of comparisons does not exceed ⌊log2(n)⌋ + 1.
- Best case: O(1), if the target element happens to be right in the middle.

### Why exactly O(log n)

After each comparison, the search range is halved. The size of the remaining range is n, n/2, n/4, ..., 1. The number of steps k is such that n / 2^k ≤ 1, that is, k ≥ log2(n). Hence the number of iterations is proportional to log2(n).

### Space complexity

- Iteratively: O(1) - a fixed number of pointers/indices is used.
- Recursively: O(log n) - the recursion depth equals the number of halvings.

### Requirements and limitations

- The data must be sorted by the same criterion you use to compare elements.
- Random access to elements in O(1) is required. On linked lists, binary search loses its point and turns into O(n).
- The order's stability and the comparison function must be transitive (key monotonicity).

### How many steps is that

1. n = 16: 16 → 8 → 4 → 2 → 1 - 5 comparisons (≈ log2(16) + 1).
2. n = 1,000,000: about 20 comparisons.

### Pitfalls

- Overflow when computing the middle: use mid = left + ((right - left) >> 1), not (left + right) / 2.
- Loop bounds: for the range [left, right] the condition is left ≤ right; for the half-open interval [left, right), it is left < right.
- Duplicates: plain binary search returns any matching index; for the first/last occurrence, use the lower_bound/upper_bound variants.

## Code examples

### Iterative binary search (JS)

```javascript
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = left + ((right - left) >> 1); // safer than (left + right) >> 1
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1; // not found
}

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

### First occurrence (lower_bound)

```javascript
function lowerBound(arr, target) {
  let left = 0, right = arr.length; // half-open interval [left, right)
  while (left < right) {
    const mid = left + ((right - left) >> 1);
    if (arr[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left; // first index where arr[i] >= target
}

// Usage for "the first equal element"
const b = [1, 3, 3, 3, 5, 8];
const idx = lowerBound(b, 3);
const exists = idx < b.length && b[idx] === 3; // true
console.log(idx, exists); // 1 true
```

### Binary search on the answer (monotonic predicate)

A technique for when the target value is the minimum/maximum satisfying a monotonic condition. The complexity is also O(log R) over the range R of possible answers.

```javascript
// Example: minimum capacity to ship weights within days (a classic problem)
function minCapacity(weights, days) {
  let left = Math.max(...weights);
  let right = weights.reduce((s, x) => s + x, 0);
  const can = cap => {
    let need = 1, sum = 0;
    for (const w of weights) {
      if (sum + w > cap) { need++; sum = 0; }
      sum += w;
    }
    return need <= days;
  };
  while (left < right) {
    const mid = left + ((right - left) >> 1);
    if (can(mid)) right = mid; else left = mid + 1;
  }
  return left;
}
```

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

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.