The Best Style on Writing Binary Search

I have been thinking about writing something for my English blog for a long time. However it was really a problem for me to decide what to write. Finally I decide to write something that I'm learning.

The principle of binary search is really simple. It's just to find the middle of the array and compare it with the given number to narrow down the range until find the number. But when implying it, the problem occurs: what if there are even numbers in the array? what if the array is empty? what if there is no given number in the array? Though it is a simple algorithm, to write a non-bug binary search is difficult.

So what is the best style on writing binary search? Maybe the one in C++ STL <algorithm>:

template<class ForwardIt, class T, class Compare>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    ForwardIt it;
    typename std::iterator_traits<ForwardIt>::difference_type count, step;
    count = std::distance(first, last);

    while (count > 0) {
        it = first;
        step = count / 2;
        std::advance(it, step);
        if (comp(*it, value)) {
            first = ++it;
            count -= step + 1;
        }
        else
            count = step;
    }
    return first;
}

Let me simplify it into the minimum Python Code:

def lower_bound(array, first, last, value): # return the position of the first one no less than value in [first, last)
    while first < last: # the range is not empty
        mid = first + (last-first) // 2 # prevent overflow
        if(array[mid] < value): fist = mid + 1;
        else: last = mid;
    return first # return last is OK, because when break out, the first is always equal to the last

The key idea is the to search in [first, last). In 1982, Dijkstra commentted:

To denote the subsequence of natural numbers 2, 3, ..., 12 without the pernicious three dots, four conventions are open to us
a) 2 ≤ i < 13
b) 1 < i ≤ 12
c) 2 ≤ i ≤ 12
d) 1 < i < 13

Are there reasons to prefer one convention to the other? Yes, there are. The observation that conventions a) and b) have the advantage that the difference between the bounds as mentioned equals the length of the subsequence is valid. So is the observation that, as a consequence, in either convention two subsequences are adjacent means that the upper bound of the one equals the lower bound of the other. Valid as these observations are, they don't enable us to choose between a) and b); so let us start afresh.

There is a smallest natural number. Exclusion of the lower bound —as in b) and d)— forces for a subsequence starting at the smallest natural number the lower bound as mentioned into the realm of the unnatural numbers. That is ugly, so for the lower bound we prefer the ≤ as in a) and c). Consider now the subsequences starting at the smallest natural number: inclusion of the upper bound would then force the latter to be unnatural by the time the sequence has shrunk to the empty one. That is ugly, so for the upper bound we prefer < as in a) and d). We conclude that convention a) is to be preferred.

When dealing with a sequence of length N, the elements of which we wish to distinguish by subscript, the next vexing question is what subscript value to assign to its starting element. Adhering to convention a) yields, when starting with subscript 1, the subscript range 1 ≤ i < N+1; starting with 0, however, gives the nicer range 0 ≤ i < N. So let us let our ordinals start at zero: an element's ordinal (subscript) equals the number of elements preceding it in the sequence. And the moral of the story is that we had better regard —after all those centuries!— zero as a most natural number.

And for the next I will explain why to write like this and what the problems may caused in other styles.

1. why mid=first+(last-first)//2 but not mid=(first+last)//2 ?

Because when the array is too large, first + last may cause overflow. In order to prevent this we changed it to first+(last-first)//2

1. why this algorithm is right?

Because when in the while loop the following conditions are always meeted:

1. first < last and the range is not empty always.
2. in the left of [first, last), the values of the number are always smaller than value.
3. in the right of [first, last), the values of the number are always not smaller than value.

so when the program breaks out, the first meets the last, the left part always smaller than value and the right part always not smaller than value. So first is the first element no less than value.

But...what if the loop never ends?

if we didn't update first to mid + 1 but mid, maybe the loop will never ends. This is a common problem when writing binary search and needs to be considered carefully.

Well...these are my thoughts. Hope I could write more English in the future.