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.

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

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

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
}