二分查找

zhou2023-10-112023-10-11

二分查找

二分查找也被称为折半搜索。

简介

在一个升序的数组里，它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找

算法实现

STL

`lowr_bound`和`upper_bound`

C++ 标准库中实现了查找首个不小于给定值的元素的函数 std::lower_bound 和查找首个大于给定值的元素的函数 std::upper_bound，二者均定义于头文件 <algorithm> 中。

二者均采用二分实现，所以调用前必须保证元素有序。

bsearch 函数

bsearch 函数为 C 标准库实现的二分查找，定义在 <stdlib.h> 中。在 C++ 标准库里，该函数定义在 <cstdlib> 中。qsort 和 bsearch 是 C 语言中唯二的两个算法类函数。

bsearch 函数相比 qsort（排序相关 STL）的四个参数，在最左边增加了参数「待查元素的地址」。之所以按照地址的形式传入，是为了方便直接套用与 qsort 相同的比较函数，从而实现排序后的立即查找。因此这个参数不能直接传入具体值，而是要先将待查值用一个变量存储，再传入该变量地址。

于是 bsearch 函数总共有五个参数：待查元素的地址、数组名、元素个数、元素大小、比较规则。比较规则仍然通过指定比较函数实现，详见排序相关 STL。

bsearch 函数的返回值是查找到的元素的地址，该地址为 void 类型，找不该元素时会返回NULL。

与lowr_bound函数的区别就是，如果有重复值，bsearch函数返回的不一定是首个不小于定值的元素，有可能是中间的

建议使用lowr_pound和upper_bound函数

1	auto it = lower_bound(prefixSum.begin(), prefixSum.end(), newTarget);

手写代码模板

int l,r;
vector<int>nums,target;
while(l<r){
    //这里可能有溢出,所以要写成下面这个格式
    int mid=l+(r-l)>>1;
 	//
    if(nums[mid]<target){
        l=mid+1;
    }else{
        r=mid;
    }
}

三种写法

闭区间

int lower_bound(vector<int> &nums, int target) {
        int left = 0, right = (int) nums.size() - 1; // 闭区间 [left, right]
        while (left <= right) { // 区间不为空
            // 循环不变量：
            // nums[left-1] < target
            // nums[right+1] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1; // 范围缩小到 [mid+1, right]
            else
                right = mid - 1; // 范围缩小到 [left, mid-1]
        }
        return left; // 或者 right+1
    }

左闭右开区间

int lower_bound2(vector<int> &nums, int target) {
    int left = 0, right = nums.size(); // 左闭右开区间 [left, right)
    while (left < right) { // 区间不为空
        // 循环不变量：
        // nums[left-1] < target
        // nums[right] >= target
        int mid = left + (right - left) / 2;
        if (nums[mid] < target)
            left = mid + 1; // 范围缩小到 [mid+1, right)
        else
            right = mid; // 范围缩小到 [left, mid)
    }
    return left; // 或者 right
}

开区间

int lower_bound3(vector<int> &nums, int target) {
        int left = -1, right = nums.size(); // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // nums[left] < target
            // nums[right] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid; // 范围缩小到 (mid, right)
            else
                right = mid; // 范围缩小到 (left, mid)
        }
        return right; // 或者 left+1
    }

三分法

如果需要求出单峰函数的极值点，通常使用二分法衍生出的三分法求单峰函数的极值点。

三分法与二分法的基本思想类似，但每次操作需在当前区间 [l,r]（下图中除去虚线范围内的部分）内任取两点 lmid,rmid(lmid < rmid)（下图中的两蓝点）。如下图，如果 f(lmid)<f(rmid)，则在 [rmid,r]（下图中的红色部分）中函数必然单调递增，最小值所在点（下图中的绿点）必然不在这一区间内，可舍去这一区间。反之亦然。