二分查找思想
看了y总的讲解,第一次知道二分并不一定是要排序才能应用。
只要可以根据要搜索的值把代搜索区间分为两半,即可应用。
模板
以Leetcode 34题为例
本题是要寻找排序数组中给定值的第一个和最后一个元素的位置。
设目标值=x
首先以上面说的二分思想,我们要搜索两个位置,也就是要用两次二分,虽然它们的值相等。对于目标值的开始位置,它的右边包括它本身的区间满足>=x ,它的左边(不过包括它本身)满足<x,这时我们要找的位置位于右边的区间末尾,注意我们划分的这两个区间没有重叠,即每次都在闭区间内搜索。同理对于x的结束位置也可以将区间划分为两半,左边(包括x的位置)<=x, 右边(不包括x)>x。分别根据划分的区间,写函数来计算开始和结束位置。
代码如下
1 | vector<int> searchRange(vector<int>& nums, int target) { |
第二段 mid=(right+left+1)/2 是因为这时我们所要查找的位置位于左边区间的右边界,所以满足条件的话left=mid,如果不+1,则会造成无限循环,参考两个元素的例子。
与上面类似,也是模板题。这里我们要查找的位置的定义是:大于等于target的第一个数,也就是右侧区域的左边界。
代码如下:
1 | class Solution { |
注意这里要考虑边界,如果target不在数组中,则返回target要插入的位置,这是符合我们查找>=target的第一个数的定义的。但是如果数组中所有数都小于target,target插入的位置则会超过右边界,这时二分结束时,l的值应该是指向数组的最后一个元素的。所以要在二分循环退出后进行判断。如果l指向的位置的数大于等于target,那么查找正确,否则就是出现了上面说的边界情况,返回右边界+1。
上面的是整数二分,所要根据查找的位置将区间分为两个不相交的区间,而浮点数就没有这种问题。直接
1 | if(...) left=mid; |
浮点数二分用于求平方根或者三次方根。
以求三次方根为例https://www.acwing.com/problem/content/792/
1 | #include<iostream> |
注意这时选择的范围不能是0-x,因为有正有负,而且(0,1)的三次方根是比x大的。