What if the array contains duplicates of the target?

Standard binary search returns the index of any one of the duplicates. To find the first or last occurrence, modify the condition when $A[M] = T$ to continue searching the left or right half, respectively.

What if the array is sorted in descending order?

Reverse the comparison logic: if $A[M] T$, search the right half ($L = M + 1$).

Can binary search be applied to linked lists?

No. Binary search requires $O(1)$ random access to elements to efficiently find the middle index, which linked lists do not support.

How to perform binary search on a sorted array

Binary search locates a target value within a sorted array by repeatedly dividing the search interval in half. It applies exclusively to arrays or lists that are already sorted in ascending or descending order.

The setup

Define the array $A$ of $n$ elements, indexed from $0$ to $n-1$ , and the target value $T$ . Initialize two pointers: $L = 0$ for the left bound and $R = n-1$ for the right bound.

The steps

While $L \le R$ , compute the middle index $M = \lfloor \frac{L + R}{2} \rfloor$ . 2. If $A[M] = T$ , return $M$ . 3. If $A[M] < T$ , the target must be in the right half, so set $L = M + 1$ . 4. If $A[M] > T$ , the target must be in the left half, so set $R = M - 1$ . 5. If the loop terminates without returning, the target is not in the array (return $-1$ ).

Checking the result

Verify that $A[ ext{result}] = T$ . If the algorithm returns $-1$ , verify manually that $T$ does not exist between $A[L]$ and $A[R]$ at the point of loop termination.

Common errors

Integer overflow can occur when calculating $M$ using $L + R$ for very large arrays. Use $M = L + \lfloor \frac{R - L}{2} \rfloor$ instead. Off-by-one errors in loop conditions (using $<$ instead of $\le$ ) or bounds updates (using $L = M$ instead of $L = M + 1$ ) lead to missed elements or infinite loops.

Worked example

Find $T = 7$ in the sorted array $A = [1, 3, 5, 7, 9, 11]$ .

Initial state: $n = 6$ , $L = 0$ , $R = 5$ . Iteration 1: $M = \lfloor (0 + 5)/2 \rfloor = 2$ . $A[2] = 5$ . Since $5 < 7$ , set $L = 2 + 1 = 3$ . Iteration 2: $L = 3$ , $R = 5$ . $M = \lfloor (3 + 5)/2 \rfloor = 4$ . $A[4] = 9$ . Since $9 > 7$ , set $R = 4 - 1 = 3$ . Iteration 3: $L = 3$ , $R = 3$ . $M = \lfloor (3 + 3)/2 \rfloor = 3$ . $A[3] = 7$ . Since $7 = 7$ , return $M = 3$ . The index of target $7$ is $3$ .

FAQ

Run your own problem

Answer form

References: Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein) · The Algorithm Design Manual (Skiena)