# Binary Search

# Binary Search

Binary search finds a target value in a **sorted sequence** by repeatedly dividing the search space in half. At each step, it compares the target with the middle element and discards half of the remaining elements.

This reduces the problem size exponentially, which leads to logarithmic time complexity.

## Problem

Given a sorted array $A$ of length $n$ and a value $x$, find an index $i$ such that

$$
A[i] = x
$$

If no such index exists, return $-1$.

## Key Idea

Maintain a search interval $[l, r]$. At each step:

* Compute midpoint $m$
* Compare $A[m]$ with $x$
* Eliminate half of the interval

## Algorithm

```id="b1x92p"
binary_search(A, x):
    l = 0
    r = length(A) - 1

    while l <= r:
        m = l + (r - l) // 2

        if A[m] == x:
            return m
        else if A[m] < x:
            l = m + 1
        else:
            r = m - 1

    return -1
```

## Example

Let

$$
A = [1, 3, 5, 7, 9, 11]
$$

and

$$
x = 7
$$

Steps:

| step | l | r | m | A[m] | action     |
| ---- | - | - | - | ---- | ---------- |
| 1    | 0 | 5 | 2 | 5    | move right |
| 2    | 3 | 5 | 4 | 9    | move left  |
| 3    | 3 | 3 | 3 | 7    | found      |

Return index $3$.

## Correctness

At each step, the algorithm maintains the invariant:

* If $x$ exists in $A$, then it must lie within $[l, r]$

Each comparison removes half of the remaining candidates while preserving this invariant. When $l > r$, the interval is empty, so $x$ does not exist.

## Complexity

| case    | comparisons                    | time        |
| ------- | ------------------------------ | ----------- |
| best    | $1$                            | $O(1)$      |
| worst   | $\lfloor \log_2 n \rfloor + 1$ | $O(\log n)$ |
| average | $O(\log n)$                    | $O(\log n)$ |

Space complexity:

* Iterative: $O(1)$
* Recursive: $O(\log n)$ due to call stack

## Requirements

Binary search requires:

* The array must be sorted
* Random access to elements

If either condition fails, correctness or efficiency breaks.

## Common Variants

Binary search generalizes to:

* Lower bound (first $\ge x$)
* Upper bound (first $> x$)
* First true in monotone predicate
* Search on answer space

These variants rely on the same invariant: monotonicity.

## Implementation

```id="k39f2q"
def binary_search(a, x):
    l, r = 0, len(a) - 1
    while l <= r:
        m = l + (r - l) // 2
        if a[m] == x:
            return m
        elif a[m] < x:
            l = m + 1
        else:
            r = m - 1
    return -1
```

```id="z8s7dh"
func BinarySearch(a []int, x int) int {
    l, r := 0, len(a)-1
    for l <= r {
        m := l + (r-l)/2
        if a[m] == x {
            return m
        } else if a[m] < x {
            l = m + 1
        } else {
            r = m - 1
        }
    }
    return -1
}
```