【Leetcode刷题】二分查找

Leetcode刷题】二分查找"/>

【Leetcode刷题】二分查找

二分法

二分法的两个主要实现方式：双开区间和双闭区间（单开单闭区间则是比较雷同的做法了，而且其不太适用到其他算法，暂不考虑）。

双开区间

二分查找（Q704)

双开区间的意思是，我们在整个实现过程中，只考虑mid指针元素的值和target的关系，不考虑head和tail是否和target相等，因为我们要预先保证它们俩都和target不相等。
因此算法步骤是：

1. 如果target处在区间外，直接返回-1；
2. 如果整个数组的head或者tail等于target，直接返回对应的坐标；
3. 处理(head, tail)这个开区间，对应的条件判断和终止判断就应该是：
   条件判断：
   如果mid指向元素等于target，直接返回mid；
   如果mid指向元素小于target，head=mid；
   如果mid指向元素大于target，tail=mid；
   终止判断：
   tail-head=1；
   可以看出来，条件判断保证了head和tail始终不会和target相等，终止判断是区间为空的时候。

def binarySearch(nums: list, target: int) -> int:# (head, tail)head = 0tail = len(nums) - 1if nums[head] > target or nums[tail] < target:return -1if nums[head] == target:return headif nums[tail] == target:return tailwhile(tail - head > 1):mid = (head + tail) // 2if nums[mid] == target:return midelif nums[mid] < target:head = midelif nums[mid] > target:tail = midreturn -1

二分range搜索（Q34）

双开区间可以拿来求解Q34这道题，具体做法是二分+递归：

1. 通过二分法找到其中一个与target相等的位置anchor点，并且得到找到anchor点时对应的head和tail；
2. 以anchor点为分割点，将head和tail分成左半和右半，搜索并找到左侧端点和右侧端点；

这里有一个非常重要的点，第一步里面，要得到找到anchor点时对应的head和tail，这里就需要两个条件：

1. head和tail必须在终止的时候也是保持大小关系的；
2. 我们要保证head和tail的值不是target，也就是说，要把搜索的range缩小到head和tail之间，如果不是的话，如果我们找到的是[head, tail]，那么head-1或者tail+1指向的也可能是target；

第二步里面，我们要使用递归方法，不断地根据新的mid对左半或者右半区间进行划分，找到左侧端点和右侧端点，因此终止条件很重要，那就是当head和tail组成的小区间只有两个元素或者只有一个元素的时候，注意边界条件（如左子树搜索时，最后如果只剩head和tail，要判断一下head是否和target相等，以免漏掉这个head）。代码如下：

def searchRange(nums: list, target: int) -> list:length = len(nums)if length == 0:return [-1, -