2019.05.04 | Something else | 0 Like | 0 comment.

I have a lot of devices: my two laptops, my android phones, my pad and my kindle, and I always read the same book in different devices. Therefore it has been a problem for a long time for me to sync my books across different devices. And after my tries these days, the final solution came up: to use OneDrive for sync books, calibre-web on server side to offer webview, calibre on PC to read, Moon+ on Android to read and GDrive for android to sync reading process.

See More ->


2019.04.17 | Algorithm | 0 Like | 0 comment.

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

See More ->