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; O(1) in the best case (if the target is right in the middle).
- Memory: O(1) for an iterative implementation; O(log n) for a recursive one (due to the call stack).
- Number of comparisons: roughly ⌈log2 n⌉ (within the range ⌈log2 n⌉...⌈log2 n⌉+1).

## Detailed breakdown

### Prerequisites for using it

- The data is sorted by the comparison key.
- There is random access to elements in O(1) (for example, an array/dynamic array).
- The comparator defines a strict order and is transitive (no contradictions).

### Why O(log n)

At each step, binary search halves the current range and discards one of the halves. After k steps, at most n / 2^k elements remain. It stops when 1 or 0 elements are left, that is, n / 2^k ≤ 1 ⇒ k ≥ ⌈log2 n⌉. Hence the time is O(log n).

### Cases by time

- Best case: O(1) - the target value is right in the middle.
- Average case: O(log n) - averaging over a uniform distribution of the target index.
- Worst case: O(log n) - it takes the maximum possible number of steps to narrow the range down to one.

### Memory

An iterative implementation uses a constant number of variables - O(1). A recursive one adds call nesting of depth about ⌈log2 n⌉ - O(log n) in memory.

### Code (JavaScript)

```javascript
// Iterative binary search: index of the found element or -1
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    // Safe midpoint computation (protects against overflow in languages with 32-bit ints)
    const mid = left + ((right - left) >> 1);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1; else right = mid - 1;
  }
  return -1;
}

// lowerBound: the first index i where arr[i] >= target
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;
}

// upperBound: the first index i where arr[i] > target
function upperBound(arr, target) {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = left + ((right - left) >> 1);
    if (arr[mid] <= target) left = mid + 1; else right = mid;
  }
  return left;
}

// The first occurrence index of target, or -1 (for arrays with duplicates)
function firstOccurrence(arr, target) {
  const i = lowerBound(arr, target);
  return i < arr.length && arr[i] === target ? i : -1;
}

// The last occurrence index of target, or -1
function lastOccurrence(arr, target) {
  const j = upperBound(arr, target) - 1;
  return j >= 0 && arr[j] === target ? j : -1;
}

// Insertion position that keeps the array sorted (if the element is absent)
function insertionIndex(arr, target) {
  return lowerBound(arr, target);
}

// Usage examples
const a = [1, 2, 4, 4, 5, 9, 12];
console.log(binarySearch(a, 5));        // 4
console.log(firstOccurrence(a, 4));     // 2
console.log(lastOccurrence(a, 4));      // 3
console.log(insertionIndex(a, 6));      // 5
```

### Frequent mistakes and nuances

- Wrong loop bounds: use a consistent half-open interval [l, r) or a closed one [l, r] with the matching stop condition.
- Computing the midpoint as (l + r) / 2 can overflow in languages with 32-bit integers; l + (r - l) / 2 is safer.
- Infinite loops from an incorrect bound update (for example, r = mid instead of r = mid - 1 in a closed interval).
- Duplicates: a basic search returns any matching index; use lowerBound/upperBound for the first/last occurrence.
- Unsorted data or structures without O(1) access (for example, linked lists) are not suitable for classic binary search.

### Comparison with linear search

Linear search is O(n). Binary search is O(log n). For example, at n = 1,000,000 binary search takes about 20 steps, while linear search may need up to a million comparisons.

### Summary

Binary search runs in O(log n) time and O(1)/O(log n) memory (iterative/recursive). This is achieved by repeatedly halving the search range.

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

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.