Leetcode刷题】二分查找"/>
【Leetcode刷题】二分查找
二分法
二分法的两个主要实现方式:双开区间和双闭区间(单开单闭区间则是比较雷同的做法了,而且其不太适用到其他算法,暂不考虑)。
双开区间
二分查找(Q704)
双开区间的意思是,我们在整个实现过程中,只考虑mid指针元素的值和target的关系,不考虑head和tail是否和target相等,因为我们要预先保证它们俩都和target不相等。
因此算法步骤是:
- 如果target处在区间外,直接返回-1;
- 如果整个数组的head或者tail等于target,直接返回对应的坐标;
- 处理(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这道题,具体做法是二分+递归:
- 通过二分法找到其中一个与target相等的位置anchor点,并且得到找到anchor点时对应的head和tail;
- 以anchor点为分割点,将head和tail分成左半和右半,搜索并找到左侧端点和右侧端点;
这里有一个非常重要的点,第一步里面,要得到找到anchor点时对应的head和tail,这里就需要两个条件:
- head和tail必须在终止的时候也是保持大小关系的;
- 我们要保证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, -
更多推荐
【Leetcode刷题】二分查找
发布评论