二分查找的模板

本文主要是介绍二分查找的模板，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

（一）当题目的目的是查找“序列中是否存在满足某条件的元素”，使用此方法最好

A[]为严格递增序列,left为二分下界，right为二分上界，x为想要查询的数,左闭右闭区间[left,right]查找.查找成功返回位置，查找失败返回-1.

int binarySearch(int A[], int left, int right, int x) {
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (A[mid] == x) return mid;
        else if (A[mid] > x) right = mid - 1;
        else left = mid + 1;
    }
    return -1;
}
int main() {
    const int n = 10;
    int A[n] = { 1,3,4,6,7,8,10,11,12,15 };
    printf("%d %d\n", binarySearch(A, 0, n - 1, 6), binarySearch(A, 0, n - 1, 9));
    return 0;
}//返回3  -1

当二分上界超过int数据类型的一半，则语句mid = (left + right) / 2;left+right便有可能超出int导致溢出，所以一般使用mid=left+(right+left)/2这条语句等价代替，避免溢出。

（二）进一步进行讨论，如果查找的数组有多个重复元素，求出序列中第一个大于等于x的位置L;以及第一个大于x的元素的位置R,这样x序列存在的区间便是左闭右开区间[L,R)。L和R也可以理解为假设序列中存在x，则x应该在的位置。
1.先来求序列中第一个大于等于x元素的位置

int lower_bound(int A[], int left, int right, int x) {
    int mid;
    while(left < right) {
        mid = (left + right) / 2;
        if (A[mid] >= x) right = mid;
        else left = mid + 1;
    }
    return left;//此时left=right,返回夹出来的位置。
}
int main() {
    const int n = 10;
    int A[n] = { 1,3,4,6,7,8,10,11,12,15 };
    printf("%d %d\n", lower_bound(A, 0, n, 6), lower_bound(A, 0, n , 15));
    return 0;
}//返回3 9  

观察可知求序列中第一个大于等于x元素的需求与第一个判断句if (A[mid] >= x)相照应。

2.再求序列中第一个大于x的元素的位置

int upper_bound(int A[], int left, int right, int x) {
    int mid;
    while (left < right) {
        mid = (left + right) / 2;
        if (A[mid] > x) right = mid;
        else left = mid + 1;
    }
    return left;//此时left=right,返回夹出来的位置。
}
int main() {
    const int n = 10;
    int A[n] = { 1,3,4,6,7,8,10,11,12,15 };
    printf("%d %d\n", upper_bound(A, 0, n - 1, 6), upper_bound(A, 0, n, 16));
    return 0;
}//返回3  10

观察可知求序列中第一个大于x元素的需求与第一个判断句if (A[mid] >x)相照应。
（三）
解决“寻找有序序列第一个满足某条件的元素的位置”问题的固定模板。
二分区间为左闭右闭的[left,right],初值必须能覆盖解的所有可能取值。

int solve(int left, int right) {
     int mid;
    while (left < right) {
        mid = (left + right) / 2;
        if (条件满足) right = mid;//条件成立，第一个满足条件的元素的位置<=mid;
                                                 //在[left,mid]接着查找
        else left = mid + 1; //条件不成立，则第一个满足条件的元素的位置>mid;
                                       //在[mid+1,right]接着查找
    }
    return left;//返回夹出来的位置。
}

解决“寻找有序序列第一个满足某条件的元素的位置”问题的固定模板。
二分区间为左开右闭的（left,right],初值必须能覆盖解的所有可能取值。
初值必须能覆盖解的所有可能取值，并且left比最小取值小1；

int solve() {
    int mid;
    while (left + 1< right) {
        mid = (left + right) / 2;
        if (条件满足)  right = mid;//条件成立，则第一个满足条件的元素的位置<=mid
                                                   //在(left,mid]接着查找
        else left = mid ;//条件不成立，则第一个满足条件的元素的位置>mid
                                                  //在(mid,right]接着查找
    }
    return right;//返回夹出来的位置。此时right=left+1
}

（四）
如果想要寻找最后一个满足条件c元素的位置，可以先求第一个满足条件!c的位置然后，将该位置减一。（*待补充）。

这篇关于二分查找的模板的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！