二分查找
1. 写一个正确的二分查找程序
需要注意的是,二分查找有许多注意的地方,比如循环中止条件是什么,left
和 right
初始值是什么。下面以Leetcode 704
号问题,写一个基本的二分查找算法。
1 | /** |
2. left的意义是什么
我们可以看最后要跳出循环时,也就是left = right
时,此时mid = left = right
,如果数组中存在这个元素,自然返回mid
索引,如果不存在呢,回到以下代码:
1 | if(nums[mid] > target){ |
left
的位置恰好就是该元素插入到该数组的位置。当nums[mid] > target
时,如果要将target
插入到数组中,要将nums[mid]
元素向后移一个位置,空出来的位置就是应该插入的位置,也就是left
指向的位置。如果小于呢,left = mid + 1
,此时left
会向后移一位,恰好又是应该插入的位置。
由此解决Leetcode 35
号问题。
1 | /** |
3. 其他相关问题
3.1 在排序数组中查找元素的第一个和最后一个位置
这是Leetcode 34
号问题。
1 | /** |
3.2 第一个错误的版本
这是Leetcode 278
号问题。
1 | /** |
还是看一下边界条件,当left = right = mid
, 如果isBadVersion(mid) == true
成立,表明这就是第一个错误版本,返回left
;否则,表明mid
是一个正确版本,那么left = mid + 1;
left
就是第一个错误的版本。
3.3 寻找峰值
这是Leetcode 162
号问题
1 | /** |
类似的还有Leetcode 852
号问题。
1 | /** |
注意:以上两道题在边界处理方面有所不同,应当注意取分。
考虑852
号问题边界情况,最后一次循环已经到了“峰顶”元素,且此时left = right = mid
,由于A[mid]
为“峰顶”元素,且其后面至少有一个元素,那么A[mid] > A[mid+1]
(mid+1
没有越界),因此执行right = mid - 1
,又right < left
,跳出循环,返回left
。
Leetcode 1095
号问题。
1 | /** |
3.4 Pie
杭电oj 1969
题目大意为:
给定n个不同半径的派(高度均为1,口味互不相同),有f+1个人,求一个最大体积V,使得这n个派可以分为f+1份(不可以多个不同口味的派拼起来凑成V)。可以发现最大体积一定不会大于最大派的体积Max,因此在区间[0,Max]中进行二分搜索就可以。
1 |
|
4. 利用二分法求解方程
杭电oj 2199
说的是给定函数8x4+7x3+2x2+3x+6==Y,针对输入的不同的Y,求出x在区间[0,100]上的解,要求最终x精确到小数点后4位。
1 |
|
杭电oj 2899
给定函数f(x)=6x7+8x6+7x3+5x2−yx,x∈[0,100],对于给定的不同的y值,求出f(x)在[0,100]上的最小值(精确到小数点后4位)。
1 |
|
5. 三分法
二分法能够有效解决有序序列的问题,然而当一个序列先增大后减小(或者先减小后增大)即存在一个峰值时,就要用到三分的思想了。三分和二分有点像,三分是在left和right指针区间内,设置mid1、mid2两个指针,即mid1与mid2将[left,right]区间三等分。之后根据具体问题更新left和right指针位置,即可能:left=mid1或者right=mid2。
- 例子:求解函数f(x)=x2−4x+3,x∈[0,5]上的极小值。
1 |
|