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
查看更多 ->
