# Binary Search
Binary Search is a searching algorithm that finds a target in a sorted, randomly-accessible sequence by repeatedly halving the candidate range.
**Time:** O(log n)
**Space:** O(1)
**Difficulty:** EASY
*[Interactive widget: binary-search-visualizer (Binary Search Visualizer) — open the HTML page]*
Canonical: https://scaleengineer.com/algorithms/binary-search
---
On a sorted array, each probe of the middle cell throws away half of the indices that might still hold the target\. One comparison decides which half to keep\. Repeat that, and a billion values reduce to thirty probes\.

The figure above runs exactly this loop\. `LO` and `HI` mark the bounds of the live range, `MID` marks the cell under comparison, and the bracket above the cells shows the current `[lo, hi]`\. The target cell carries a small tick until the probe lands on it\. Cells fade as they leave the range\. Press play and watch one full search, then read on\.

## The invariant that does the work

Binary search keeps one promise: if the target is in the array, it sits in the live range `[lo, hi]`\. The promise holds at the start, because the range is the whole array\. It holds after every probe, because each discard removes only indices that cannot match\. And when the range finally runs empty, the promise turns into a proof: no live index remains, so the target is not in the array\.

Sorted order is what makes a discard safe\. Everything left of `mid` is less than or equal to the mid value\. Everything right of `mid` is greater than or equal to it\. So when the mid value is smaller than the target, nothing at `mid` or to its left can match, and that whole half can go\.

This is also the precondition\. Run the loop on an unsorted array and a discard can drop the half that holds the target\. The figure enforces the rule: type an unsorted array and it rejects the input instead of running a broken search\. If your data arrives unsorted, sort it once and search it many times\. [Merge sort](/algorithms/merge-sort) is one way to get that order\.

## How one probe works

Keep two inclusive bounds, `lo` and `hi`, starting at `0` and `n - 1`\. While `lo <= hi`, probe the midpoint:

1. Set `mid` to the index halfway between `lo` and `hi`\.
2. If the mid value equals the target, stop\. You have an index\.
3. If the mid value is smaller than the target, set `lo` to `mid + 1`\.
4. If the mid value is larger than the target, set `hi` to `mid - 1`\.

When `lo` rises past `hi`, the range is empty\. Report a miss\.

```python
def binary_search(a, target):
	lo, hi = 0, len(a) - 1
	while lo <= hi:
		mid = lo + (hi - lo) // 2
		if a[mid] == target:
			return mid
		if a[mid] < target:
			lo = mid + 1
		else:
			hi = mid - 1
	return -1
```

Three details in this loop carry the invariant\. The range is inclusive, so the test is `lo <= hi`\. A one\-element range still deserves a probe\. The updates move past `mid`, because `mid` was just compared\. Leave `mid` in the range and a two\-cell range can loop forever\.

The midpoint is `lo + (hi - lo) // 2`, not `(lo + hi) // 2`, because the sum can overflow a fixed\-width integer when both bounds are large\. The figure uses `(lo + hi) >> 1` because its demo arrays stay small\. Use the overflow\-safe form in production code\.

## A walkthrough, probe by probe

Take the figure's starting array, `[2, 5, 8, 12, 17, 23, 29, 34]`, with target `23`\. The live range starts at `[0, 7]`\.

1. Probe index `3`\. The cell holds `12`\. Because `12` is smaller than `23`, nothing at or left of index `3` can match\. Set `lo` to `4`\. The range becomes `[4, 7]`, and the four discarded cells fade\.
2. Probe index `5`\. The cell holds `23`\. That is the target\. The search ends\.

Two probes for eight values, and the left half never gets a second look\. The figure below starts from the same array and target\. Press play in the above interactive element and it runs exactly these steps\.

*[Interactive widget: binary-search-visualizer — open the HTML page]*

A miss runs on the same rule\. In either figure, type `16` into the target field\. Press play\. The probes hit `12`, then `23`, then `17`\. Each discard is sound, so when the range collapses after the third probe, the collapse itself is the answer: `16` is not in the array\.

Then make it yours\. Click any cell to search for its value, or type a sorted array of up to ten numbers with a new target\. The walk restarts, and the invariant holds every time\.

## Why the probe count is logarithmic

Each probe cuts the live range to at most half its previous length\. After `k` probes, at most `n / 2^k` cells remain\. The loop ends when that count drops below one, which happens after about `log2 n` probes\. Where the target sits changes which probes run and whether the loop stops early\. A first\-probe hit is the best case\. A miss, or a target hiding in a corner, runs the full count\.

The worst case grows slowly:

| Values in the array | Worst\-case probes |
| --- | --- |
| `8` | `4` |
| `1,000` | `10` |
| `1,000,000` | `20` |
| `1,000,000,000` | `30` |

Space stays flat\. The iterative loop stores three integers, so extra space is `O(1)`\. A recursive version pays `O(log n)` stack frames instead, one per probe\.

This is why sorted data is such a strong asset\. Sorting costs `O(n log n)` once, and every lookup after that costs almost nothing\. Linear search asks nothing up front and pays `O(n)` on every lookup\.

## The same trick without an array

Binary search needs two things: a range of candidate answers and a question with a monotonic answer\. Monotonic means every no sits left of every yes: once the answer flips to yes, it never flips back\. Ask the question at the midpoint and each probe still discards half\. The array is the special case where the candidates are indices and the question is *“is the mid value smaller than the target?”*

The pattern pays off wherever testing a candidate is cheaper than listing every candidate:

- First bad version: find the earliest commit where the tests start to fail\.
- Capacity: find the smallest ship capacity that still moves every package on time\.
- Roots: find the largest integer whose square does not exceed `n`\.

Duplicates need one change\. A hit on `23` in `[17, 23, 23, 23, 29]` can land on any of the three copies\. To find the first copy, record the hit and keep searching left: set `hi` to `mid - 1`\. That variant is the lower bound: the first index whose value is at least the target\. It ships next to the classic loop in the implementation panel on this page\.

## When to reach for it

Reach for binary search when three things hold:

- The data is sorted, or you can sort it once and search many times\.
- You can read any index in constant time\. Arrays qualify\. Linked lists do not, because reaching the middle means walking half the list\.
- Lookups dominate the work\. If every query needs a full pass over the data anyway, sorting buys nothing\.

Skip it for a single search through unsorted data\. Sorting first costs `O(n log n)`, and one linear scan costs `O(n)`\. The prepayment pays off only across many lookups\.

The practice problems below all reduce to one idea: probe the middle, discard the half that cannot match, and trust the invariant\. Start with an easy one and watch for the moment the problem tells you which half to keep\.

## Code examples

### Binary search Classic (JavaScript)

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

  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);

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

  return -1;
}
```

### Binary search Classic (Python)

```python
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return -1
```

### Binary search Classic (Java)

```java
public static int binarySearch(int[] arr, int target) {
    int lo = 0;
    int hi = arr.length - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

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

    return -1;
}
```

### Binary search Classic (C)

```c
int binary_search(const int *arr, size_t n, int target) {
    size_t lo = 0;
    size_t hi = n;  /* half-open [lo, hi) avoids underflow when n == 0 */

    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;

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

    return -1;
}
```

### Binary search Classic (CPP)

```cpp
int binarySearch(const std::vector<int>& arr, int target) {
    int lo = 0;
    int hi = static_cast<int>(arr.size()) - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

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

    return -1;
}
```

### Binary search Classic (CSharp)

```csharp
public static int BinarySearch(int[] arr, int target)
{
    int lo = 0;
    int hi = arr.Length - 1;

    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;

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

    return -1;
}
```