Binary-Search

Problem statement

An often seen problem is to find given elements in a list. If the list is sorted, we can determine the elemenet without checking every element in the list.

An Example: We have an array $a$. The elements of the array are sorted ascending, so for all elements $a[i] \le a[i+1]$. We assume that every element is unique, therefore the elments of the list are strictly greater ($a[i] < a[i+1]$). We would like to find the position of the element $x$ in the given array.

Solution

Whenever we compare an elment at positon $k$ with the given value $x$ there are 3 possibilities: 1. We are lucky and $x=a[k]$, our search has ended. 2. More likely is, that $x < a[k]$ … 3. … or $x > a[k]$.

Because we assume our array is sorted, we can state that when $x > a[k]$, $x$ is also greater than all previous elements ($a[k-1], a[k-2], ... a[0]$). For our search we therefore can exclude all these elements. The same argument holds for the other direction. When $x < a[k]$ all elements with a higher index are also greater than $x$ and we can exclude them.

In the case of binary-search we save two indices, the beginning and the end of our sorted search area. Now we determine the middle element for our comparison. If our element is greater, we move the beginning to this element. If our element is smaller, then we move the end of our search area to the middle. We repeat this process with our search are that now is exactly half as big as before till we either find our element $x$ or we have no elements in our range (begin = end).

Implementation

/*
 * int[]     a     : sorted array
 * int       x     : wanted Element
 * long long start : begin of our search area
 *                   0 if we look through the whole array
 * long long end   : end of our search area
 *                   at most index of the last element
 */
int binary_search(int[] a, int x, int start, int end){
    while(start<=end){             //as long as there are other possibilites
        int middle=(start+end)/2;  //determine middle element
        if(a[middle]==x)           //found element x
            return middle;
        else if(x<a[middle])       //x is smaller
            end=middle-1;          //reset end
        else                       //x is greater
            start=middle+1;        //move begin
    }
    //no elements in our search range
    //x is no element of a[]
    return -1;
}

Memory- and runtimeanalysis

We have to save a fixed amount of values. It does not matter if we look through $10$ or $1000$ element, we only need the upper and lower bound of our search range and the middle element. So we need only a constant amount of memory $O(1)$.

The runtime is a bit more complex to determine. Summarized the runtime is $O(k\cdot\log(n))$. $k$ is the runtime of our comparison operator. When we compare elementary datatypes this will be $k=1$, the runtime of binary search is therefore $O(log(n))$. If we compare strings, lists or bigint’s $k$ depends on the length of the objects.