做腰椎核磁证网站是 收 七/北京线上教学
最基础的二分查找 Leetcode704
- 循环直至最终结果被找到或者找不到
- 如果查找不到的话，每次循环都要更新mid
- 更新mid通过更新high 或者low来实现
于是自然而然顺着意识流写下了如下代码：
while low<=high: # 原始代码，走完所有的值mid = (low+high)//2;num = nums[mid]if(target==num):return midelif(target<num):high = mid - 1else:low = mid + 1return -1
本质是缩小查找区间 Leetcode278
- 利用二分查找实现，假如mid的调用结果是true，说明mid后面的版本（包括mid）都是错误的，否则mid前面的内容(包括mid)都是正确的。本质上是一个缩小查找区间的过程；
- 如果mid所指版本是正确的，那么所求版本应在[mid+1,high]；
- 如果mid所指版本是错误的，所求版本应在[low,mid]；
- 最后low 和high重合的索引就是第一个错误的测试例子索引。这里关于重合，我要专门说一下，以前总认为是
while(low<high)的循环终止结果，其实并不是，原因在这。这道问题最终之所以low 能够和high重合的原因是要查找的值一定在序列中。
代码
low,high = 1,nwhile low < high :mid = low + (high-low)//2if isBadVersion(mid):high = midelse:low = mid + 1return low # 因为low 和high重合，所以返回low/high均正确。
二分的思维方式 Leetcode35
代码
low,high = 0,len(nums)-1while low < high:mid = low + (high-low)//2num = nums[mid]if target == num:return midelif target < num:high = mid - 1else:low = mid + 1if target <= nums[low] :return low else:return low + 1
ASK with more thinking
- while循环体内为什么不是
low<=high,而是low<high？ - 为什么看了许多教程，别人都在讨论返回low的普适性，而我的代码并未讨论？
Try to answer
- 【二分问题的思考方式】因为二分是一个不断缩小目标值所在的有序区间的过程，因此while循环执行到最后处理的情况都如出一辙，因此可以采用假设法。具体可以采用三种假设情况。
-
有序区间,两个数字足矣 -
左端点 -
右端点
- 实操一下思考过程。（假设有序区间为[7,10],左端点7,右端点10,计算出m = 0）
-
有序区间 ：target=8，,更新low = 1，此时low==high,结束 -
左端点 ：target = 0,更新high = -1,此时low==0,结束 -
右端点：target = 100,更新low = 1,此时low==high，结束
可见，当while（low<high）时，退出循环的条件不一定是low==high,也有可能high<low，但是所有的情况却都满足：
if target <= nums[low] :return low else:return low + 1
- 假如
while(low<=high)，同样重复上述思考过程，可以得到结论———所有的情况都满足return low可以得到正确结果。
SUMMARY
- low<high OR low<=high
- 当循环退出时，low==high?
Leetcode704 target在序列中,low<=high,遍历有序序列中所有值
Leetcode278 target在序列中,low<high,循环退出条件是low==high,返回low（第一个错误版本）
Leetcode35 target不在序列中,low<high
INSPIRATION OR REFERENCE
分类讨论的思想/枚举