HappyCpp

一个不会打代码的程序猿

0%

二分查找

发表于 分类于 阅读次数： 评论数：

二分查找

二分查找

二分查找算法是运用分治策略的典型例子。
他是一种效率较高的查找算法，但是要求数组中的元素按顺序排列。其最坏时间复杂度为O(logn)。

一、二分查找算法的基本思想是：将n个元素分成个数大致相同的两个区间，取mid=(l+r)>>1;如果a[mid]==target,则返回mid下标即为target元素在数组中的下标,否则当a[mid]< target,说明在当前左区间端点到mid中不存在target元素,则我们要让l=mid+1(注意：这里l=mid会引起死循环)，同理，当a[mid] > target,说明右区间端点到mid中不存在target元素,所以我们要让r=mid-1;如果我们找不到,最后返回-1即可。

附代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[10005];
int binarysearch(int x,int l,int r) {
    while(l<=r) {
        int mid=(l+r)>>1;
        if(a[mid]==x)
            return mid;
        else if(a[mid]>x)
            r=mid-1;
        else
            l=mid+1;
    }
    return -1;
}
int main() {
    int n,target;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    scanf("%d",&target);
    int pos=binarysearch(target,1,n);
    printf("%d\n",pos);
    return 0;
}

那么在c++的STL中下给我们提供了一个函数binary_search;
函数使用方法：binary_search(arr[],arr[]+size,target);
参数说明：
arr[]：数组首地址
size：数组元素个数
target:需要查找的值
函数功能： 在数组中以二分法检索的方式查找，若在数组(要求数组元素非递减)中查找到target元素则真，若查找不到则返回值为假。

二、同理我们可以查询在数组中大于等于/大于target的第一个元素。
我们依然令mid=(l+r)>>1,如果a[mid]>=target,这里我们思考一下r=mid还是r=mid-1呢？
我们可以看到a[mid]是大于等于target的,说明mid是可以满足这个条件的,那么这个端点是不能舍弃的，所以r=mid。
否则当a[mid]< target时,我们再来看一下l=mid还是l=mid+1呢？
a[mid]< target,说明mid不满足这个条件,所以舍弃这个端点,l=mid+1,最后我们判断一下最后剩下的元素是否满足条件即可。

附代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int lowerbound(int x,int l,int r) {
    while(l<r) {
        int mid=(l+r)>>1;
        if(a[mid]>=x)
            r=mid;
        else
            l=mid+1;
    }
    if(a[l]>x)
        return l;
    return -1;
}
int upperbound(int x,int l,int r) {
    while(l<r) {
        int mid=(l+r)>>1;
        if(a[mid]>x)
            r=mid;
        else
            l=mid+1;
    }
    if(a[l]>x)
        return l;
    return -1;
}

c++的STL中也给我们提供了方法,分别是lower_bound和upper_bound
函数使用方法：lower_bound(arr[], arr[]+size , target);
参数说明：
arr[]：数组首地址
size：数组元素个数
target:需要查找的值
函数功能：lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于target的第一个元素位置(注意是地址)。如果所有元素都小于target，则返回last的位置。

函数使用方法：upper_bound(arr[], arr[]+size , target);
参数说明：
arr[]：数组首地址
size：数组元素个数
target:需要查找的值
函数功能：函数upper_bound()返回的在前闭后开区间查找的关键字的上界，返回大于val的第一个元素位置,(注意是地址)。如果所有元素都小于等于target，则返回last的位置。

这里以lower_boun函数举例说明：
设一个数组arr[]={1,3,3,5,7};
我要查找第一个大于等于3的元素位置,
int pos=lower(arr,arr+5,3)-arr;
所以pos=1。

三、我们还可以查询在数组中小于等于/小于target的第一个元素。
这里注意：我们要让mid=(l+r+1)/2;考虑这样一种情况,最后只剩下a[i],a[i+1],假设我们不加1,那么mid=i,如果a[mid]< target,那么l=mid=i,
r=mid+1=i+1,就会造成死循环。加上1后,mid=i+1,若a[mid]< target,那么l=r=mid=i+1,跳出循环。若a[mid]>=target,那么l=r=mid-1=i,跳出循环。

附代码：

1
2
3
4
5
6
7
8
9
10
int search(int x,int l,int r) {
    while(l<r) {
        int mid=(l+r+1)>>1;
        if(a[mid]<x)
            l=mid;
        else
            r=mid-1;
    }
    return l;
}

四、总结
后两种情况的循环条件是l< r,因为我们的区间查找思路是不断舍弃不可能是解的区间,最后只剩下一个数就是我们的解。
而第一种情况就算最后只剩下一个数也有可能不是解,所以使用小于等于。
+查找精确值，循环条件是小于等于；查找满足情况的最大最小值，循环条件是小于
+查找满足条件的最大数,mid=(l+r+1)>>1；查找满足条件的最小数,mid=(l+r)>>1;