它是如何工作的？

在最简单的形式中，二分查找 对具有指定左索引和右索引的连续序列进行操作。这就是所谓的 查找空间。

二分查找维护查找空间的左、右和中间指示符，并 比较查找目标或将查找条件应用于集合的中间值；

如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。
如果查以空的一半结束，则无法满足条件，并且无法找到目标。

二分查找一般由三个主要部分组成：

预处理 —— 如果集合未排序，则进行排序。
二分查找 —— 使用循环或递归在每次比较后将查找空间划分为两半。

后处理 —— 在剩余空间中确定可行的候选者。

模板 I——仅访问当前节点而不需要访问左右节点

def binarySearch(nums, target):
 """
 :type nums: List[int]
 :type target: int
 :rtype: int
 """
 if len(nums) == 0:
     return -1
 left, right = 0, len(nums) - 1
 while left <= right:
     mid = (left + right) // 2
     if nums[mid] == target:
         return mid
     elif nums[mid] < target:
         left = mid + 1
     else:
         right = mid - 1
 # End Condition: left > right
 return -1

用于查找 仅需要访问数组中当前索引元素的情况。

关键属性

二分查找的最基础和最基本的形式。
查找条件可以在**不与元素的两侧进行比较**的情况下确定（或使用它周围的特定元素）。
不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。

区分语法

初始条件：left = 0, right = length-1
终止：left > right
向左查找：right = mid-1

向右查找：left = mid+1

模板 II——访问当前节点即其直接右邻节点

def binarySearch(nums, target):
  """
  :type nums: List[int]
  :type target: int
  :rtype: int
  """
  if len(nums) == 0:
      return -1
  left, right = 0, len(nums)
  while left < right:
      mid = (left + right) // 2
      if nums[mid] == target:
          return mid
      elif nums[mid] < target:
          left = mid + 1
      else:
          right = mid
  # Post-processing:
  # End Condition: left == right
  if left != len(nums) and nums[left] == target:
      return left
  return -1

用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件。

关键属性

一种实现二分查找的高级方法。
查找条件需要访问元素的直接右邻居。
使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
保证查找空间在每一步中至少有 2 个元素。
需要进行后处理。当你剩下 1 个元素时，循环/递归结束。需要评估剩余元素是否符合条件。

区分语法

初始条件：left = 0, right = length
终止：left == right
向左查找：right = mid

向右查找：left = mid+1

模板 III——需要访问当前节点及其相邻的左右节点

def binarySearch(nums, target):
  """
  :type nums: List[int]
  :type target: int
  :rtype: int
  """
  if len(nums) == 0:
      return -1

  left, right = 0, len(nums) - 1
  while left + 1 < right:
      mid = (left + right) // 2
      if nums[mid] == target:
          return mid
      elif nums[mid] < target:
          left = mid
      else:
          right = mid

  # Post-processing:
  # End Condition: left + 1 == right
  if nums[left] == target: return left
  if nums[right] == target: return right
  return -1

用于搜索 需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。

关键属性

搜索条件需要访问元素的直接左右邻居。
使用元素的邻居来确定它是向右还是向左。
保证查找空间在每个步骤中至少有 3 个元素。
需要进行后处理。当剩下 2 个元素时，循环/递归结束。需要评估其余元素是否符合条件。

区分语法

初始条件：left = 0, right = length-1
终止：left + 1 == right
向左查找：right = mid
向右查找：left = mid

模板总结

这 3 个模板的不同之处在于：
左、中、右索引的分配。
循环或递归终止条件。
后处理的必要性。

模板 #1 和 #3 是最常用的，几乎所有二分查找问题都可以用其中之一轻松实现。模板 #2 更高级一些，用于解决某些类型的问题。

模板 #1(left <= right)

二分查找的最基础和最基本的形式。
查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）。
不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。

模板 #2(left < right)：
一种实现二分查找的高级方法。
查找条件 需要访问元素的直接右邻居。
使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
保证查找空间在每一步中至少有 2 个元素。
需要进行后处理。当你剩下 1 个元素时，循环/递归结束。需要评估剩余元素是否符合条件。

模板 #3(left + 1 < right)：
实现二分查找的另一种方法。
搜索条件 需要访问元素的直接左右邻居。
使用元素的邻居来确定它是向右还是向左。
保证查找空间在每个步骤中至少有 3 个元素。
需要进行后处理。当剩下 2 个元素时，循环/递归结束。需要评估其余元素是否符合条件。
参考链接
https://leetcode-cn.com/explore/learn/card/binary-search/208/background/832/

https://leetcode-cn.com/explore/learn/card/binary-search/208/background/834/
https://leetcode-cn.com/explore/learn/card/binary-search/212/template-analysis/847/

二分查找

它是如何工作的？

模板 I——仅访问当前节点而不需要访问左右节点

模板 II——访问当前节点即其直接右邻节点

模板 III——需要访问当前节点及其相邻的左右节点

模板总结

模板 #1(left <= right)

模板 #2(left < right)：

模板 #3(left + 1 < right)：

参考链接