二分查找

最常见的二分查找

704. 二分查找

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
    #循环版本
	left,right=0,len(nums)-1
	while left<=right:
		mid=left+(right-left)//2
		if nums[mid]==target:
			return mid #返回下标
		elif nums[mid]<target: #则目标值在右半段
			left=mid+1 # 已知mid不是，就没有必要了
		else:
			right=mid-1
	return -1

	#递归版本
	def bsearch(left,right,target):
		mid=left+(right-left)//2
		if left>right:return -1
		if nums[mid]==target:return mid
		elif nums[mid]<target: return bsearch(mid+1,right,target)
		else: return bsearch(left,mid-1,target)
	return bsearch(0,len(nums)-1,target)

寻找左边界

278. 第一个错误的版本

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1：

输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

示例 2：

输入：n = 1, bad = 1
输出：1

如果使用range(n)遍历会产生溢出问题
代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

  def firstBadVersion(self, n):
      """
      :type n: int
      :rtype: int
      """
      # 遍历:超时
      # for i in range(n):
      #     if isBadVersion(i+1):
      #         return i+1
      # 二分
      left,right=1,n
      while left<=right:
       mid=left+(right-left)//2
       if isBadVersion(mid):#如果这是个错误版本，则第一个错误版本一定在[left,mid-1]之间
        right=mid-1
    else:
	    left=mid+1
return left	        

寻找左右边界

LCR 172. 统计目标成绩的出现次数

示例 1：

输入: scores = [2, 2, 3, 4, 4, 4, 5, 6, 6, 8], target = 4
输出: 3

示例 2：

输入: scores = [1, 2, 3, 5, 7, 9], target = 6
输出: 0

原理

1. 初始化： 左边界 left=0 ，右边界 right=len(scores)−1。
2. 循环二分： 当闭区间[left,right]无元素时跳出；
   1. 计算中心点:mid=left+(right-left)//2
   2. if scores[mid]<target:说明target在闭区间[mid+1,right]中，则left=mid+1
   3. if scores[mid]>target:说明target在闭区间[left,mid-1]中，则right=mid-1
   4. if scores[mid]==target:则需要分情况讨论
      1. 如果是找左边界，则左边界一定在较小的那一边，因此左边界一定在[left,mid-1]区间，则right=mid-1
      2. 如果是找右边界，则left=mid+1

代码

1. 未优化版本

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

   def countTarget(self, scores, target): """ :type scores: List[int] :type target: int :rtype: int """ # 寻找左边界 left,right=0,len(scores)-1 while left<=right: mid = left+(right-left)//2 if scores[mid]<target: # 说明target在[mid+1,right]中 left=mid+1 elif scores[mid]>target: right=mid-1 elif scores[mid]==target: #如果相等，说明左边界在[left,mid-1] right=mid-1 final_left=left # 寻找右边界 left,right=0,len(scores)-1 while left<=right: mid = left+(right-left)//2 if scores[mid]<target: # 说明target在[mid+1,right]中 left=mid+1 elif scores[mid]>target: right=mid-1 elif scores[mid]==target: #如果相等，说明左边界在[left,mid-1] left=mid+1 final_right=left return final_right-final_left