Binary Search
你会得到一个按升序排列且没有重复值的整数列表 nums，以及一个整数 target。返回 target 在 nums 中的索引，从 0 开始计数；如果它不在列表中，则返回 -1。目标是将时间复杂度控制在 O(log n)，这意味着你不能逐个查看所有元素。
函数
- numsinteger-array
- 已排序的不重复整数列表
- targetinteger
- 要查找的值
- 返回值integer
- nums 中 target 的索引，如果不存在则为 -1
约束条件
1 ≤ nums.length ≤ 104-104 ≤ nums[i], target ≤ 104nums按严格递增顺序排列，因此每个值只出现一次。
示例
- 输入
- nums = [-7, -2, 0, 4, 9, 15, 23]target = 9
- 输出
- 4
- 解释
nums[4]是 9。搜索会先查看索引 3（值为 4，太小），然后查看索引 5（值为 15，太大），接着查看索引 4，并在那里找到 9。
- 输入
- nums = [1, 3, 5, 8, 13, 21]target = 10
- 输出
- -1
- 解释
- 10 会处于 8 和 13 之间，而它们都不是 10，所以 10 不在列表中。搜索范围会不断缩小，直到
lo超过hi，然后函数返回-1。
进阶
如果 nums 中的值可能重复，如何仍在 O(log n) 时间内返回 target 第一次出现的索引？
提示
逐个打开提示，每个都会多透露一点。
列表已排序。如果你将
target与中间的一个元素进行比较，这能告诉你它一侧的所有元素什么信息？如果
nums[mid] < target，那么nums[mid]及其左侧的所有元素都太小了，所以target只能在右侧。一次比较就能排除一半的候选项。保留两个索引
lo和hi，标记列表中仍可能包含target的部分。将它与中间位置的值进行比较，然后把lo或hi移到中间位置之外。找到target，或者lo越过hi时停止。
题解
列表已经排好序，因此只需将目标值与中间元素比较一次，就能判断哪一半仍可能包含 target。每一步都排除一半候选项，因此，对于包含 10^4 个元素的列表，最多只需比较 14 次，而不是 10,000 次。
从左向右扫描
思路
按顺序将每个元素与 target 比较，并返回第一个匹配项；如果循环结束后仍未找到，则返回 -1。无论列表是否已排序，这种做法都正确。
它完全不利用元素的顺序，因此对于包含 10^4 个元素的列表，最多需要进行 10,000 次比较：复杂度为 O(n)，而不是题目要求的 O(log n)。
算法
- 对于从 0 到
n-1的每个索引i，将nums[i]与target进行比较。 - 如果它们相等，则返回
i。 - 循环结束后，返回
-1。
def search(nums, target):
for i, value in enumerate(nums):
if value == target:
return i
return -1使用两个索引进行二分查找
思路
保留两个索引 lo 和 hi，并始终遵守一个约定：如果列表中有 target，它的索引就位于两者之间，且包含两端。当 nums[mid] 小于 target 时，由于列表已排序，直到 mid 的所有元素也都更小，因此 lo 可以移到 mid 之后。基于同样的原因，较大的 nums[mid] 会让 hi 移到 mid 之前。每次移动后，这个约定都仍然成立。
如果找不到 target，范围会不断缩小，直到 lo 超过 hi。此时范围为空，因此按照这个约定，target 不在任何位置。每一步都会将范围缩小一半，因此循环最多运行约 log2(n) + 1 次，额外占用两个索引的内存。
算法
- 将
lo = 0和hi = n-1设为初始值。 - 当
lo ≤ hi时，计算mid = lo + (hi - lo) / 2。 - 如果
nums[mid]等于target，则返回mid。 - 如果
nums[mid] < target，则设置lo = mid + 1；否则设置hi = mid - 1。 - 循环结束时，返回
-1。
def search(nums, target):
lo, hi = 0, len(nums) - 1 # target, if present, sits in nums[lo..hi]
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1 # nums[mid] and everything left of it is too small
else:
hi = mid - 1 # nums[mid] and everything right of it is too big
return -1
易错点和边界情况
- 当
hi从最后一个索引开始时，在lo < hi的情况下循环。循环结束时会有一个候选项未检查，所以nums = [5]且target = 5时会返回-1。 - 在使用闭区间时，将
lo更新为mid或将hi更新为mid。当lo和hi相邻时，mid等于lo，区间永远不会缩小，导致无限循环。 - 当找不到
target时返回lo。循环结束后，lo是插入位置，是一个有效索引，而不是-1。 - 忘记在 Lua 和 R 中进行偏移。它们的列表从 1 开始，所以你返回的索引是位置减去 1。
常见问题3
二分查找的时间复杂度是多少？
O(log n) 时间。每次比较都会将仍可能包含目标值的范围缩小一半，因此包含 10^9 个元素的列表最多需要 30 次比较。迭代版本只需要 O(1) 的额外空间。
二分查找应该用迭代还是递归？
两种写法都正确，运行时间都是 O(log n)。递归版本使用 O(log n) 的栈空间；移动 lo 和 hi 的循环使用 O(1) 的空间。面试官通常更期待你使用循环。
计算中间索引时，如何避免溢出？
请写成 mid = lo + (hi - lo) / 2，而不是 (lo + hi) / 2。两种写法得到的索引相同，但对于 32 位整数，当索引超过约 1.07 × 10^9 时，求和 lo + hi 会溢出。Python 和 Ruby 的整数没有上限，因此在这两种语言中，简写形式是安全的。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def search(nums, target):
# 在这里编写代码测试 #1
测试 #2
参数
nums = [-7, -2, 0, 4, 9, 15, 23] target = 9
预期输出
4