Jianbo Dai's

lc704.二分查找

 
  • Sep 25, 2021

题目链接

二分查找虽然基础，但是很多细节都需要注意的，看了一下知乎上一个回答，来把它理一理清楚。

回答链接 首先，给出一个求”非降序范围[first, last)内第一个不小于value的值的位置”模板，再稍微进行一些解释：

def lower_bound(array, first, last, value):  # 求非降序范围[first, last)内第一个不小于value的值的位置
		while first < last:  # 搜索区间[first, last)不为空
				mid = first + (last - first) // 2  # 防溢出
				if array[mid] < value:
						first = mid + 1
				else:
						last = mid
		return first  # last也行，因为[first, last)为空的时候它们重合

首先，搜索区间强烈建议用左闭右开！这样能够使加减1的步骤到最少（因为这符合python区间的使用习惯）同时，配套的我们使用<而不是<=。另外，如果你想求的不是“第一个不小于value的值的位置”，而是任意等于value的值的位置，你可以在更新[first, last)区间前先检查array[mid] == value是否成立。mid起初的计算方式是为了防止溢出。然后，更新first和last位置的时候要记住必须用严格的方式，也就是first要变成mid+1而非mid，last要变成mid而非mid+1。最后，返回的时候不需要纠结，first和last是重合的，返回任意都可以。

回到题目本身，注意到我们要找的是等于value的值，所以要做一点改动，就是在更新区间前先检查array[mid]与value是否相等，若相等则返回mid，若最后找不到值就返回-1 。这个解法的时间复杂度是O（log（N）），空间复杂度是O（1）。

python:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        res = self.bisect(nums, 0, len(nums), target)
        return res

    def bisect(self, nums, first, last, target):
        while first < last:
            mid = first + (last - first) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                first = mid + 1
            elif nums[mid] > target:
                last = mid
        return -1
Search