bisection algorithm

This algorithm falls into the class of "divide and conquer" algorithms. The bisection algorithm divides a problem into two parts (ideally equal but not strictly required) choosing the best part (which contains the solution) and discarding the other. Then iterates until you have the solution you desire.

The best example of this is finding a specific item in an array of items. First, we have the precondition that the array must be sorted so that when we look at an element in the array, we can decide if the solution is before or after it. Then, we apply the formula

    middle = floor ((top + bottom) / 2)

where top and bottom are the current top and bottom positions in the array and middle is computed to be the median between them.

This gives us two partitions: [top, middle)¹ and (middle, bottom)².

Now, under the condition that the solution is before the middle item, we simply set bottom to middle. Or, if the solution occurs after the middle item we set top to middle + 1. And iterate.

As you can see, the solution is always in the range [top, bottom)¹. And, the range is constantly shrinking (converging to a solution).

The advantage of bisection is that is O(log n). That is to say that if you have n items in an array then it will take on the order of log n steps to find the item of interest.

For example, to searching an array of "type" in C++, we write:

template <class type>
int bisection_on_an_array
 (const type * array, int size_of_array, const type & key)
{
    int top = 0;
    int bottom = size_of_array;

    while (top < bottom)
    {
        int middle = (top + bottom) / 2;
        if (array [middle] < key)
            top = middle + 1;
        else
        /* if (array [middle] >= key) */
            bottom = middle;
    }

    return top;
}

This version of the code will return an index that points to the first of (possibly) duplicate items in the array by virtue of the equals clause in >=.

If the item is not found in the array, this code will return an index to the position it would be inserted (above) to keep the array in sorted order. The returned value is on the range [0, size_of_array]³.

Personally, I never use the bsearch function in the C standard library because 1) if doesn’t return the insertion position if the search fails and 2) the algorithm is so simple it fits naturally into the flow of logic of larger, more complicated algorithms if written in line. Then there is the whole argument against passing pointers to functions around.

Note: this is also a generalization of the bisection method for finding roots.

---

¹ […,…) denotes a range inclusive of the first element and exclusive of the last
² (…,…) denotes a range exclusive of the first and last elements
³ […,…] denotes a range inclusive of the first and last elements

---

Thanks to hobyrne for his comments and suggestions.