The Binary Search Algorithm

This page has been migrated to Medium

The Binary Search Algorithm is a search algorithm that works for sorted collections (e.g. sorted arrays). It takes as input a collection, the length of that collection and an element to find, and gives as output the index of the element in the collection (if it exists).

This algorithm is as efficient as easy to learn due to its simplicity.

This algorithm does only O(log n) comparisons.

On the other hand, it only works for sorted collections, making it restricted to some specific cases.

Pseudocode

The pseudocode for the algorithm is the following:

    function BSA(A, n, T):
        L := 0
        R := n − 1
        while L <= R:
            m := floor((L + R) / 2)
            if A[m] < T:
                L := m + 1
            else if A[m] > T:
                R := m - 1
            else:
                return m
        return unsuccessful

Let’s explain this pseudocode:

  • The algorithm takes as input an array A, the length of the array n and the element to search T;
  • We initialize two variables: L to 0 and R to n-1, namely the index to the first and the last element to the array A;
  • We iterate until L becomes equal or greater than R, that is when we iterated over the whole array;
  • We initialize m to be the floor or (L+R)/2, namely the index of the element at the middle of the array;
  • Then we compare the element at the index m to the desired element T:
    • if A[m] is lower than T we should search T in the greater half of the array: the one in [m+1, R];
    • if A[m] is greater than T we should search T in the lower half of the array: the one in [L,m-1];
    • otherwise A[m] is equal to T and we can return m because we found the element.

Python

Let’s have a look at the BSA using Python.

As you may see, the BSA written in Python is very similar to the pseudocode. We return -1 when we cannot find the desired element.

Go

The Go version of the BSA is the following:

Unlike the Python version, this code does not look similar to the pseudocode because of Go’s strong typing, which forces us to do 2 casts (line 5). Also in the Go implementation we return -1 if we cannot find the element T. Due to the simplicity of the algorithm itself, no other consideration has to be made.

C

The C version of the BSA could be the following:

The C implementation looks quite similar to the Go implementation but does not have casts because C has weak typing.

This is my first blog post.