有人说,90%的程序员都手写不出正确的二分查找
没错,我就是那90%
c++的标准库里只提供了binary_search(),lower_bound(),upper_bound()三个函数,缺点就是,只能在数组或者vector这样的线性数据结构上二分
所以就需要整理一下二分的用法和代码
1,binary_search(arr[],arr[]+size,key,cmp)
功能:找到正好等于key的元素,成功则返回位置,否则返回数组末尾指针
注意,给出的最后一个参数是比较函数的指针,如果不给出,默认调用标准库中的less()函数,其实就是小于号。
这个是最好写的,不需要考虑左右边界或者失配的问题
(伪)代码:
int binary_search(arr[],arr[]+size,key,cmp) { int left = 0; int right = nums.length - 1; while(left <= right) { int mid = (right + left) / 2; if(equal(arr[mid],key)) return arr[]+mid; else if (less(nums[mid],target)) left = mid + 1; else right = mid - 1; } return arr[]+size; }
2,lower_bound(arr[],arr[]+size,key,cmp)
这个函数的功能是找出第一个大于等于key的值,可以简记为左边界,和上一个函数不同的是,除非key值大于全部数组中的值,才会返回arr[]+size,否则一定会返回一个有效值。
(伪)代码:
int lower_bound(arr[],arr[]+size,key,cmp){ int left = 0; int right = size-1; while (left <= right) { int mid = (left + right) / 2; if(less(arr[mid],key)){ left = mid + 1; } else{ right = mid - 1; } } return arr[]+left; }
注意,这个函数就比上一个难写很多,比如left,right为什么要小于等于,最后要返回的是left还是right,等等
3,upper_bound(arr[],arr[]+size,key,cmp)
这个函数的功能是找出大于key的第一个值的位置,简称右边界
int upper_bound(arr[],arr[]+size,key,cmp){ int left = 0; int right = size-1; //查找第一个大于key的元素 while (left <= right) { int mid = (left + right) / 2; if (less(key,a[mid])) { right = mid - 1; } else { left = mid + 1; } } return arr[]+left; }
这个函数常用于给整数开平方根,因为大于key的第一个值,减去1,就是小于等于key的最后一个值
涉及到给整数开平方根或者类似的操作的,一定记得用二分,不要自作聪明求解析解,然后转换成double,在cmath库里的函数求解,再转换回来,绝对不要!
我是不会告诉你我被昨晚的atcoder arc的B题卡了一个多小时的,天知道,1e18的数据范围,他是怎么想到构造出卡掉double+sqrt的数据的
参考资料:
https://www.cnblogs.com/kyoner/p/11080078.html