力扣hot100_二分查找(1)_python版本

一、二分查找（开区间写法）

• 如果找不到，返回的right是该插入的位置
  
• 如果找到，是返回第一个等于target的位置
  

1. def binary_search(nums, target):
2.     left, right = -1, len(nums)
3.     while left+1 < right:  
4.         # 循环不变量
5.         # nums[left] < target
6.         # nums[right] >= target
7.         mid  = (left+right) // 2
8.         if nums[mid] < target:  # 循环不变量对齐
9.             left = mid
10.         else:
11.             right = mid
12.     return right

复制代码

二、35. 搜索插入位置

• 思绪：
  标准的二分查找的
  
• 代码：
  

1. def binary_search(nums, target):
2.     left, right = -1, len(nums)
3.     while left+1 < right:  
4.         # 循环不变量
5.         # nums[left] <right
6.         # nums[right] >= right
7.         mid  = (left+right) // 2
8.         if nums[mid] < target:  # 循环不变量对齐
9.             left = mid
10.         else:
11.             right = mid
12.     return right
14. class Solution:
15.     def searchInsert(self, nums: List[int], target: int) -> int:
16.         return binary_search(nums, target)

复制代码

三、74. 搜索二维矩阵

• 思绪1：
  这道题归到二分查找是由于，可以将每一行头尾相连得到一个有序的数组，然后利用二分查找。
  
• 思绪2：
  直接利用清除法。
  
• 代码：
  

1. # 1.排除法
2. class Solution:
3.     def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
4.         m = len(matrix)
5.         n = len(matrix[0])
6.         raw_tag = -1
7.         for i in range(m):
8.             if matrix[i][-1]==target:
9.                 return True
10.             elif matrix[i][-1] > target:
11.                 raw_tag = i
12.                 break
13.             else:
14.                 pass
15.         if raw_tag == -1:
16.             return False
17.         for j in matrix[raw_tag]:
18.             if target == j:
19.                 return True
20.         return False
21.         
22. # 2.二分查找
23. class Solution:
24.     def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
25.         m, n = len(matrix), len(matrix[0])
26.         left, right = -1, m * n
27.         while left + 1 < right:
28.             mid = (left + right) // 2
29.             x = matrix[mid // n][mid % n]
30.             if x == target:
31.                 return True
32.             if x < target:
33.                 left = mid
34.             else:
35.                 right = mid
36.         return False

复制代码

四、34. 在排序数组中查找元素的第一个和末了一个位置

• 思绪：
  复用二分查找（二分查找是返回等于target的第一个位置）
  
• 代码：
  

1. def binary_search(nums, target):
2.     left, right = -1, len(nums)
3.     while left+1 < right:  
4.         # 循环不变量
5.         # nums[left] < target
6.         # nums[right] >= target
7.         mid  = (left+right) // 2
8.         if nums[mid] < target:  # 循环不变量对齐
9.             left = mid
10.         else:
11.             right = mid
12.     return right
13. class Solution:    def searchRange(self, nums: List[int], target: int) -> List[int]:        start = self.binary_search(nums, target)        if start == len(nums) or nums[start] != target:            return [-1, -1]        # 如果 start 存在，那么 end 必定存在        end = self.lower_bound(nums, target + 1) - 1        return [start, end]

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。