💾 Archived View for hanicef.me › document › binary-search captured on 2024-06-16 at 12:29:52. Gemini links have been rewritten to link to archived content

-=-=-=-=-=-=-

The binary search algorithm

Original document can be found at hanicef.me

License can be found at creativecommons.org

Description

The binary search algorithm is a simple algorithm for finding a value in an ordered list quickly. It's complexity is O(log(n)), and is easy to implement.

The algorithm works by eliminating half of all possible values in every step, until there's only one value left. For example, consider the following list:

┌───┬───┬───┬───┬───┬────┬────┐
│ 2 │ 3 │ 5 │ 8 │ 9 │ 11 │ 12 │
└───┴───┴───┴───┴───┴────┴────┘

Let's say we want to locate 5. We start by looking at the center of the list (on 8) and comparing it with the value we want to find. The process works like so:

If the value we are looking for is less than what we are currently standing on, all values on and above the one we are standing on can be eliminated.
If the value we are looking for is greater than what we are currently standing on, all values on and below the one we are standing on can be eliminated.
If the value we are looking for is equal to what we are currently standing on, the value has been found and the algorithm can terminate.

In this case, 5 is less than 8, so that means all values above it is also eliminated in the process. Thus, the values 8, 9, 11 and 12 are all eliminated. This only leaves us with 2, 3 and 5:

  Remaining       Eliminated
┌───┬───┬───┐ ┌───┬───┬────┬────┐
│ 2 │ 3 │ 5 │ │ 8 │ 9 │ 11 │ 12 │
└───┴───┴───┘ └───┴───┴────┴────┘

Now, we repeat the process with only the remaining values. In this case, the center is 3, and so we compare 3 with 5. 5 is greater than 3, so we eliminate all values below it:

Eliminated Result    Eliminated
┌───┬───┐  ┌───┐ ┌───┬───┬────┬────┐
│ 2 │ 3 │  │ 5 │ │ 8 │ 9 │ 11 │ 12 │
└───┴───┘  └───┘ └───┴───┴────┴────┘

This leaves us with only one value left, which is 5. And so, we have found the value 5 in an ordered list in just 2 iterations.

Algorithm

Assuming we want to find v in the list A, implementing binary search involving the following steps:

Set l to 0
Set r to the length of A - 1

Then repeat the following steps until either v is found or l > r:

Set i to ⌊(l + r) / 2⌋
If v = Aᵢ, v has been found at i and the algorithm can be terminated
If v < Aᵢ, set r to i - 1
If v > Aᵢ, set l to i + 1

If l > r, the value v doesn't exist in A, and the algorithm can terminate.

Example implementation

The algorithm can be implemented like this in C:

int binary_search(int *A, int n, int v) {
    int l = 0, r = n - 1, i;
    while (l < r) {
        i = (l + r) / 2;
        if (v == A[i]) {
            return i;
        } else if (v < A[i]) {
            r = i - 1;
        } else if (v > A[i]) {
            l = i + 1;
        }
    }
    return -1;
}

This function returns the index where v is located in A, or -1 if that value cannot be found.