Written by Stefanie Zbinden and Florian Wernli.

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 aa. The elements of the array are sorted ascending, so for all elements a[i]a[i+1]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]a[i] < a[i+1]). We would like to find the position of the element xx in the given array.


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

Because we assume our array is sorted, we can state that when x>a[k]x > a[k], xx is also greater than all previous elements (a[k1],a[k2],...a[0]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]x < a[k] all elements with a higher index are also greater than xx 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 xx or we have no elements in our range (begin = end).


 * 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 1010 or 10001000 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)O(1).

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

Runtimeanalysis (why log(n)?)

Every comparison cuts our search area in half. If we look at this process in reverse, the last comparison is in an area of length 2, second last comparison in are of length 4 … 11 comparison for 22 elements 22 comparisons for 44 elements 33 comparisons for 88 elements mm comparisons for 2m2^m elements Now we can see, that for nn elements we need log2(n)\log_2(n) comparisons.