对二分法思想的体会

Apale 10/14/2018

二分查找可以在有序的支持随机访问的容器中快速查找某个元素的信息时间复杂度: $O(logN)$

原始版本: 递归实现:

int binarySearch(int a[],int val,int l,int r)
{
    if(l > r) return -1;
    
    int m = l + r >> 1;
    if (val == a[m])
        return m;
    else if (val < a[m])
        return binarySearch(a,val,l,m-1);
    else
        return binarySearch(a,val,m+1,r);
}

1
2
3
4
5
6
7
8
9
10
11
12

非递归实现:

int binarySearch(int a[],int val,int l,int r)
{
    int m, ret = -1;
    while(l <= r)
    {
        m = l + r >> 1;
        if (val == a[m])
        {
            ret = m;
            break;
        }
        else if(val < a[m]) 
            r = m - 1;
        else 
            l = m + 1;
    }
    return ret;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

C++ STL中提供了三种二分查找函数 1、binary_search(f1,f2,val) 返回区间 $[f1,f2)$ 中是否存在val，存在则返回 $true$ ，否则返回 $false$ 。

2、lower_bound(f1,f2,val) 返回区间 $[f1,f2)$ 中第一个大于等于 $val$ 的元素的下标丑陋的实现：

int my_lower_bound(int a[],int val,int l,int r)
{
    int m;
    while(l < r)
    {
        m = l + r >> 1;
        if(val <= a[m])
            r = m;
        else
            l = m + 1;
    }
    return l;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

3、upper_bound(f1,f2,val) 返回区间 $[f1,f2)$ 中第一个大于 $val$ 的元素的下标丑陋的实现：

int my_upper_bound(int a[],int val,int l,int r)
{
    int m;
    while(l < r)
    {
        m = l + r >> 1;
        if(val < a[m])
            r = m;
        else
            l = m + 1;
    }
    return l;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

需要注意的是传入的区间都是左闭右开的

Blog

Choose mode

对二分法思想的体会

对二分法思想的体会