查找

二分

• 二分查找

  def binary_search(arr, target):
      left = 0
      right = len(arr) - 1
      while left <= right:
          mid = (left + right) // 2
          if arr[mid] == target:
              return mid
          else:
              if arr[mid] > target:
                  right = mid - 1
              else:
                  left = mid + 1
      return -1

• lower_bound：查找第一个大于或等于target的元素位置。

  def low_bound(arr, target):
      left = 0
      right = len(arr)-1
      while left <= right:
          mid = (left + right) // 2
          if arr[mid] >= target:
              right = mid - 1
          else:
              left = mid + 1
      return left

• upper_bound：查找第一个大于target的元素位置。

  def low_bound(arr, target):
      left = 0
      right = len(arr)-1
      while left <= right:
          mid = (left + right) // 2
          if arr[mid] > target:
              right = mid - 1
          else:
              left = mid + 1
      return left