Binary Search

---

Contents

---

Improving upon linear search

If the subarray being searched in linear search is already sorted, the searching algorithm can check the midpoint of the subarray against \(v\) and eliminate half the subarray from further consideration. Binary search repeats the procedure, halving the size of the remaining portion of the subarray each time.

Properly speaking, binary search cannot be implemented with a divide-and-conquer approach. This is because when a problem is divided into two subproblems, binary search does not need to solve both subproblems, just one.

---

Iterative/Incremental Binary Search

 INPUT    an array A[1:n] of n sorted values in ascending order and a value x in A
OUTPUT    an index i such that x = A[i]

BINARY_SEARCH(A, n, x)
1    l = 0
2    r = n - 1
3    while l < r
4        m = (l + r) / 2   // m is the average of l and r rounded down
5        if x <= A[m]
6            r = m
7        else
8            l = m + 1
9    return l

Complexity

Time

Worst Case

\(T(n) = T(n/2) + \Theta(1) = \Theta(\lg n)\)

Correctness

\(\textbf{Invariant}\)

The array is sorted in ascending order.

\(0 \le l \le r \le n - 1\)

\(x \in A[l:r]\)

\(\textbf{Initialization}\)

That the array is sorted in ascending order is in the precondition of the program.

Since \(n\) is at least \(1\) by the precondition that \(x \in A\) and since \(l\) and \(r\) are initialized to \(0\) and \(n - 1\), respectively, the inequality is satisfied:

\(0 \le (0 = l) \le (r = n - 1) \le n - 1 \iff 1 \le n\)

\(x \in A[l:r]\) because \(A[l:r]\) is the whole array and \(x \in A\) is a precondition of the program.

\(\textbf{Maintenance}\)

Since the program does not alter the array, the array remains sorted in ascending order.

Let primes denote values after iteration. It must be shown that if \(0 \le l \le r \le n - 1\) and \(x \in A[l:r]\) (i.e., the invariant is true before iteration) then \(0 \le l' \le r' \le n - 1\) and \(x \in A[l':r']\) (i.e., the invariant is true after iteration).

Since \(m\) is the average of \(l\) and \(r\) rounded down, it is known that \(l \le m \le r\). But because the loop condition \(l \lt r\) is true and the value of \(m\) is rounded down, it is known that \(l \le m \lt r\).

\(\text{Case}\,\, x \le A[m]\)

In this case \(l' = l\) and \(r' = m\) and so \(0 \le l \le m \lt r \le n - 1 \implies 0 \le l' \le r' \le n - 1\).

Since \(x \in A[l:r]\) and \(x \le A[r']\) it is the case that \(x \in A[l':r']\)

\(\text{Case}\,\, x \gt A[m]\)

In this case \(l' = m + 1\) and \(r' = r\).

\(m \lt r \implies l' = m + 1 \le r = r' \implies 0 \le l' \le r' \le n - 1\)

Since \(x \in A[l:r]\) and \(x \ge A[l']\) it is the case that \(x \in A[l':r']\). Another way to look at this is that \(x \not\in A[l:m]\) but according to the invariant \(x \in A[l:r]\) so it must be the case that \(x \in A[m + 1:r] = A[l':r']\)

\(\textbf{Postcondition}\)

For the program to be correct it must be shown that \(A[l] = x\). If the loop condition is false it is the case that \(l \not\lt r \iff l \ge r\). The loop invariant guarantees that \(l \le r\). So it must be the case that \(l = r\).

The loop invariant also guarantees that \(x \in A[l:r]\), which has now been reduced to a single element; namely, \(x\).

\(\textbf{Termination}\)

The value \(r - l\) is guaranteed by the invariant to be nonnegative, we can choose \(\text{DF}_0 = 0\)

Case \(x \in A[l:m]\): \(m \lt r \iff (m - l = r' - l') \lt r - l\)

Case \(x \in A[m + 1:r]\): \(l \lt m + 1 \iff l - r \lt (m + 1 = l') - (r = r') \iff r' - l' \lt r - l\)

The quantity \(r - l\) gets strictly smaller on every iteration as long as \(l \lt r\) and so the loop eventually terminates.

Implementations

C

// binary_search.c

#include <stdio.h>

void print_array (int A[], int n) {
  for (int i = 0; i < n; i++) {
    printf("%d ", A[i]);
  }
  printf("\n");
}

int binary_search (int A[], int n, int x) {
  int l = 0;
  int r = n - 1;

  while (l < r) {
    int m = (l + r) / 2;
    if (x <= A[m])
      r = m;
    else
      l = m + 1;
  }

  return l;
}

int main () {
  int A[] = {1, 2, 3, 4, 5};
  int n   = sizeof(A) / sizeof(A[0]);
  int x   = 4;
  int result = binary_search(A, n, x);
  
  print_array(A, n);
  printf("Value %d at index %d\n", x, result);

  return 0;
}

Python

---

Resources

• https://www.geeksforgeeks.org/binary-search/

• https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/binary-search

• https://www.cs.cornell.edu/courses/cs2112/2020fa/lectures/lecture.html?id=loopinv

• [ y ] 02-13-2023 Coding with John. “Binary Search in Java - Full Simple Coding Tutorial”.

• [ y ] 12-01-2023 Computerphile. “Bug in Binary Search - Computerphile”.

• [ y ] 11-01-2023 Computerphile. “Binary Search Algorithm - Computerphile”.

---