欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

如何写出一个正确的二分查找

程序员文章站 2022-03-15 10:23:40
...

1.二分查找

注意:本文全部例子默认数组升序排序
基于分治思想的一个很简单的算法,但若想写对,却也不是那么容易

使用条件
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列
查找过程
首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功
来源于:百度百科

我们l来看下边代码:

/**
 * 二分查找,找到该值在数组中的下标,否则为-1
 */
int binarySearch(int *a, int aSize , int key){
    int low = 0, high = aSize - 1;
    //(1)必须是"<="
    while(low<=high){
        int mid = low + (high - low) / 2;//(2)不能是int mid = (low + high)/2;
        if(a[mid]==key)
            return mid;
        else if(a[mid]>key)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

(1)处:,如果是"<"的话,low==high事程序就退出了,处于该位置的元素显然就被遗漏了。
(2)处:这是一个很著名的bug!
我们知道,数学中数有无穷大,那么求其平均数,相加除以二显然不会有任何的问题。但是在计算机中,所有的数都是以二进制的形式存储在内存中的,内存有限,所以存储的数自然不可能无穷大。
比如int型数据,现在一般是32位,第一位做符号位,所以它的范围[-231,231-1],如果low+high超过了231-1那么就溢出了,显然结果就不对了。而用我们能这种方法,便可以保证不会有溢出的风险。

2.二分查找的变种

二分查找变种主要有以下几种:

查找 第一个/最后一个 与key相等的元素
查找最后一个等于或者小于key的元素
查找最后一个小于key的元素
查找第一个等于或者大于key的元素
查找第一个大于key的元素

首先,对于这些变种的程序,总会有如下共性:

不变性:
1.循环永远是low>high时才跳出
2if(a[mid]>key) high=mid-1;.
3.if(a[mid]<key) low=mid+1;

所以,对于每个变种,我们需要考虑的情况:

1.a[mid]==key这种情况的处理
2.最后的结果保存在low中还是high中

查找第一个与key相等的元素

因为我们要找的是第一个(从左至右),所以当遇到 a[mid]==key 的情况时,肯定不能让 low=mid+1,否则就错过了第一个啦,那么只能让 high=mid-1 喽!
当然,我们再正面分析一下:

 if(a[mid]>=key)
            high = mid - 1;//为了破坏if中的条件

上述代码循环执行到最后,high指针所指向的元素一定是据key最近的小于key的元素;

if(a[mid]<key)
	low=mid+1;//为了破坏if中的条件

上述代码循环执行到最后,low指针所指向的元素一定是大于等于key这些元素中的第一个元素(从左至右)。
非正式的验证了算法的正确性,而且知道了最后的结果保存在low中.
以下是完整代码:

int binarySearch(int *a, int aSize , int key){
    int low = 0, high = aSize - 1;
    while(low<=high){
        int mid = low + (high - low) / 2;
        if(a[mid]>=key)
            high = mid - 1;
        else
            low = mid + 1;
    }
    if(low < aSize && a[low]==key) //注意这里应该防止low溢出
        return low;
    return -1;
}

查找最后一个与key相等的元素

因为要找最后一个,所以第一次遇到 a[mid]==key 时,应该选择low=mid+1;
循环破坏 a[mid]<=key 后,low所指元素为大于key的第一个元素;
循环破坏 a[mid]>key 后,high为小于等于key的最大序号。所以,最后的结果保存在high中。
完整代码如下:

int binarySearch(int *a, int aSize , int key){
    int low = 0, high = aSize - 1;
    while(low<=high){
        int mid = low + (high - low) / 2;
        if(a[mid]>key)
            high = mid - 1;
        else
            low = mid + 1;
    }
    if(high >= 0  && a[high]==key)//注意这里应该防止high溢出
        return high;
    return -1;

查找最后一个等于或者小于key的元素

就是查找最后一个与key相等的元素中的high,分析同上,代码如下:

int binarySearch(int *a, int aSize , int key){
    int low = 0, high = aSize - 1;
    while(low<=high){
        int mid = low + (high - low) / 2;
        if(a[mid]>key)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return high;

查找最后一个小于key的元素

就是查找第一个与key相等的元素的high,分析同上,代码如下:

int binarySearch(int *a, int aSize , int key){
    int low = 0, high = aSize - 1;
    while(low<=high){
        int mid = low + (high - low) / 2;
        if(a[mid]>=key)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return high;
}

查找第一个等于或者大于key的元素:

此情况其实与上边的分析差不多,就不多写废话啦。代码如下:

int binarySearch(int *a, int aSize , int key){
    int low = 0, high = aSize - 1;
    while(low<=high){
        int mid = low + (high - low) / 2;
        if(a[mid]>=key)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}

查找第一个大于key的元素

此情况其实与上边的分析差不多,就不多写废话啦。代码如下:

int binarySearch(int *a, int aSize , int key){
    int low = 0, high = aSize - 1;
    while(low<=high){
        int mid = low + (high - low) / 2;
        if(a[mid]>key)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}

总结

step1.对于所有二分,下边两个条件都是必须的,所以我们只需分析 a[mid]==key 应该给high还是low。

1if(a[mid]>key) high=mid-1;.
2.if(a[mid]<key) low=mid+1;

step2.判断输出结果,最普通的二分查找直接return;其他变种可能在low中,也可能在high中,利用上述我所说 循环的目的是为了破坏if条件句中的条件,然后该语句的否定,再加上减一这个条件,即可推出lowhigh所存序号的意义。

参考:你真的会写二分查找吗

相关标签: 二分查找