# Iterative Binary Search

# Iterative Binary Search

Iterative binary search is the standard loop-based implementation of binary search. It avoids recursion and therefore uses constant extra space. The logic maintains a shrinking interval until the target is found or the interval becomes empty.

This form is preferred in systems code because it has no call overhead and predictable control flow.

## 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$.

## Algorithm

Maintain two indices $l$ and $r$ that bound the current search interval.

```id="p7x2m1"
iterative_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 = [2, 4, 6, 8, 10, 12]
$$

and

$$
x = 10
$$

Execution:

| step | l | r | m | A[m] | action     |
| ---- | - | - | - | ---- | ---------- |
| 1    | 0 | 5 | 2 | 6    | move right |
| 2    | 3 | 5 | 4 | 10   | found      |

Return index $4$.

## Loop Invariant

At every iteration:

* If $x$ exists in $A$, then $x$ lies within the interval $[l, r]$

The update rules preserve this invariant while reducing the interval size.

## Termination

The loop terminates when:

$$
l > r
$$

At this point, the interval is empty and the target does not exist.

## Complexity

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

Space complexity:

$$
O(1)
$$

## Notes

* The midpoint is computed as `l + (r - l) // 2` to avoid integer overflow in fixed-width arithmetic.
* This version is tail-recursion-free and suitable for performance-critical paths.
* All binary search variants can be expressed in this iterative form by modifying the condition and update rules.

## Implementation

```id="a9k3c2"
def iterative_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="t2z8n4"
func IterativeBinarySearch(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
}
```