二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构

代码实现

  1. def binary_search(arr: list, target: int) -> int:
  2.     """
  3.     非递归版本
  4.     """
  5.     # 数据的范围
  6.     l, r = 0, len(arr) - 1
  8.     while l <= r:
  9.         # mid = (l+r) // 2  会存在越界
  10.         mid = l + (r - l) // 2
  11.         if arr[mid] == target:
  12.             return mid
  13.         if target > arr[mid]:
  14.             # 需要查找的数据在右边数组中
  15.             l = mid + 1
  16.         else:
  17.             # 需要查找的数据在左边的数组中
  18.             r = mid - 1
  19.     return -1
  22. def binary_search(arr: list, target: int, l: int, r: int) -> int:
  23.     """
  24.     递归版本
  25.     """
  26.     # 数据的范围
  27.     if l > r:
  28.         return -1
  30.     mid = l + (r - l) // 2
  31.     if arr[mid] == target:
  32.         return mid
  33.     if target > arr[mid]:
  34.         # 需要查找的数据在右边数组中
  35.         l = mid + 1
  36.     else:
  37.         # 需要查找的数据在左边的数组中
  38.         r = mid - 1
  40.     return binary_search(arr=arr, target=target, l=l, r=r)

二分查找变种

  1. class BinarySearch:
  3.     @staticmethod
  4.     def binary_search(arr: list, target: int) -> int:
  5.         """
  6.         二分查找非递归版本
  7.         """
  8.         # 数据的范围
  9.         l, r = 0, len(arr) - 1
  11.         while l <= r:
  12.             # mid = (l+r) // 2  会存在越界
  13.             mid = l + (r - l) // 2
  14.             if arr[mid] == target:
  15.                 return mid
  16.             if target > arr[mid]:
  17.                 # 需要查找的数据在右边数组中
  18.                 l = mid + 1
  19.             else:
  20.                 # 需要查找的数据在左边的数组中
  21.                 r = mid - 1
  22.         return -1
  24.     def binary_search_r(self, arr: list, target: int, l: int, r: int) -> int:
  25.         """
  26.         二分查找递归版本
  27.         """
  28.         # 数据的范围
  29.         if l > r:
  30.             return -1
  32.         mid = l + (r - l) // 2
  33.         if arr[mid] == target:
  34.             return mid
  35.         if target > arr[mid]:
  36.             # 需要查找的数据在右边数组中
  37.             l = mid + 1
  38.         else:
  39.             # 需要查找的数据在左边的数组中
  40.             r = mid - 1
  42.         return self.binary_search_r(arr=arr, target=target, l=l, r=r)
  44.     @staticmethod
  45.     def binary_upper(data: list, target: int) -> int:
  46.         #  寻找大于 target的最小值的下标
  47.         l, r = 0, len(data)
  48.         while l < r:
  49.             mid = l + (r - l) // 2
  50.             if data[mid] <= target:
  51.                 l = mid + 1
  52.             else:
  53.                 # 可能当前mid表示的值就是大于target 且是最小值
  54.                 r = mid
  55.         return l
  57.     @staticmethod
  58.     def binary_lower(data: list, target: int) -> int:
  59.         """ 寻找小于 target值的最大值下标 """
  60.         # 在 [l,r] 中找解
  61.         l, r = -1, len(data) -1
  62.         while l < r:
  63.             mid = l + (r - l +1) // 2
  64.             if data[mid] < target:
  65.                 l = mid
  66.             else:
  67.                 r = mid -1
  68.         return l
  70.     def binary_ceil(self, data: list, target: int) -> int:
  71.         """
  72.         天花板
  73.         找到原始数据中值为target的最大索引
  74.         如果没有返回>target的最小值索引
  75.         """
  76.         u = self.binary_upper(data, target)
  77.         if data[u - 1] == target and u - 1 >= 0:
  78.             return u - 1
  79.         return u

时间复杂度

O(logn)