lower_bound和upper_bound的实现

lower_bound和upper_bound是C++的标准函数,所以日常使用完全没有必要自己实现,不过,这么经典的算法,还是得要求自己能够秒秒钟搞定,编译运行无错.

lower_bound和upper_bound不完全等同于二分查找,它俩返回的不是有没有,而是返回新数据的插入位置.

在php和lua语言里是没有直接能拿来用的函数的,在C++和Python里是有现成代码的.

lower_bound和upper_bound的差别只有一个小于号和小于等于号的差别,以下是我的实现:

uint32_t lower_bound(int arr[], int len, int val)
{
    int beg = 0;
    int end = len;
    int mid;
    while (beg < end) {
        mid = (beg + end) >> 1;
        if (arr[mid] < val) {
            beg = mid + 1;
        } else {
            end = mid;
        }   
    }   
    return beg;
}

uint32_t upper_bound(int arr[], int len, int val)
{
    int beg = 0;
    int end = len;
    int mid;
    while (beg < end) {
        mid = (beg + end) >> 1;
        if (arr[mid] <= val) {
            beg = mid + 1;
        } else {
            end = mid;
        }   
    }   
    return beg;
}

试用举例:

int main()
{
    int arr[] = {1, 3, 4, 8, 8, 10, 12, 23};
    cout << lower_bound(arr, 8, 8) << endl;
    cout << lower_bound(arr, 8, 88) << endl;
    cout << lower_bound(arr, 8, 0) << endl;
    return 0;
}

在python里,有bisect模块可直接使用,里面实现了bisect_left,bisect_right,insort_left,insort_right四个函数, bisect_left,bisect_right就相当于lower_bound和upper_bound.

以下是bisect_left的实现,函数的描述非常清晰而优雅,可见python还是非常注重算法,再次鄙视丑陋PHP一下.

def bisect_left(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

注意一下这里的双斜杠除法,是为了确保返回值没有小数,1.0//2也会等于0.0,而不是0.5, 不过,我觉得还是有点多余,因为a[0.0]是不合法,下标必须得是整型.

更进一步考虑效率,文件末尾加上了如下代码:

try:
    from _bisect import *
except ImportError:
    pass

而实际上在python内部就已经使用C语言实现了这些函数,所以上面的python实现是不会被使用到的:

In [1]: import _bisect
In [2]: _bisect
Out[2]: <module '_bisect' (built-in)>