学习资料:https://www.hello-algo.com/

基础:二分查找元素

1
2
3
4
5
6
7
8
9
10
11
12
def binary_search(nums:[list[int]], target:int)->int:
# nums已排序
i, j = 0, len(nums)-1
while i <= j:
m = (i+j)//2
if nums[m] < target:
i = m+1
elif nums[m] > target:
j = m-1
else:
return m
return -1 # 未找到目标元素,返回-1

注意,while后的条件必须包含=,否则考虑两种情况:
1. 若最后一步执行操作为i = m+1,且m+1=j,会导致m+1不会被搜索到。
2. 若最后一步执行操作为j = m-1,且m-1=i,会导致m-1不会被搜索到。

时间复杂度:O(log  n)O(log\;n)
空间复杂度:O(1)O(1)

以上是针对双闭合区间的代码,即以区间 [i, j] 进行查找 target ;左闭右开区间则指以 [i, j) 进行查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binary_search_lcro(nums: list[int], target: int) -> int:
"""二分查找(左闭右开区间)"""
# 初始化左闭右开区间 [0, n) ,即 i, j 分别指向数组首元素、尾元素+1
i, j = 0, len(nums)
# 循环,当搜索区间为空时跳出(当 i = j 时为空)
while i < j:
m = (i + j) // 2 # 计算中点索引 m
if nums[m] < target:
i = m + 1 # 此情况说明 target 在区间 [m+1, j) 中
elif nums[m] > target:
j = m # 此情况说明 target 在区间 [i, m) 中
else:
return m # 找到目标元素,返回其索引
return -1 # 未找到目标元素,返回 -1

假设数组存在多个目标值,上述算法将返回其中任意一个索引,这具体取决于算法在搜索过程中选择的中间位置。因此,此时可考虑引入列表进行优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def binary_search_list(nums:[list[int]], target:int)->int:
result = []
i, j = 0, len(nums)-1
while i<=j:
m = (i+j)//2
if nums[m]<target:
i = m+1
elif nums[m]>target:
j = m-1 # 左闭右开则为 j = m
else:
result.append(m)
# 向左查找
left = m - 1
while left>=0 and nums[left]==target:
indices.append(left)
left -= 1
# 向右查找
right = m + 1
while right<len(nums) and nums[right]==target:
indices.append(right)
right += 1
break
return result

值得注意的是,由于 iijj 都是 int 类型,因此 i+ji+j 可能会超出 int 类型的取值范围;为避免大数越界通常采用公式 i+ji2i+\frac{j-i}{2}来计算中点。

适用场景:

  • 有序数据
  • 数组
  • 数据量较大

扩展 1:二分查找插入点

当数组中无重复元素时,只需将二分查找元素代码最后一行返回值换成 i 即可。
函数将返回最后一个小于目标值的后一个索引(当数组中最小值仍大于目标值时,索引将返回 0 ;当数组中最大值仍小于目标值时,索引将返回 len(list))。

1
2
3
4
5
6
7
8
9
10
11
12
13
def binary_search_insertion_simple(nums: list[int], target: int) -> int:
"""二分查找插入点(无重复元素)"""
i, j = 0, len(nums) - 1 # 初始化双闭区间 [0, n-1]
while i <= j:
m = (i + j) // 2 # 计算中点索引 m
if nums[m] < target:
i = m + 1 # target 在区间 [m+1, j] 中
elif nums[m] > target:
j = m - 1 # target 在区间 [i, m-1] 中
else:
return m # 找到 target ,返回插入点 m
# 未找到 target ,返回插入点 i
return i

重点:处理数组中的重复元素

这里当然也可以用列表处理(提取最大索引),但K神给出了更简便的思路。
当查找到目标索引时,我们仍然向更小的方向搜索,算法核心仍然是,我们希望返回最后一个小于目标值的后一个索引。对移动的 j 来说,就是首个小于 target 的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
def binary_search_insertion(nums: list[int], target: int) -> int:
"""二分查找插入点(存在重复元素)"""
i, j = 0, len(nums) - 1 # 初始化双闭区间 [0, n-1]
while i <= j:
m = (i + j) // 2 # 计算中点索引 m
if nums[m] < target:
i = m + 1 # target 在区间 [m+1, j] 中
elif nums[m] > target:
j = m - 1 # target 在区间 [i, m-1] 中
else:
j = m - 1 # 首个小于 target 的元素在区间 [i, m-1] 中
# 返回插入点 i
return i

我们发现,左闭右开更适合这类“边界”问题。

1
2
3
4
5
6
7
8
9
10
11
12
def binary_search_lcro_insertion(nums:[list[int]], target:int)->int:
# nums已排序
i, j = 0, len(nums)-1
while i < j:
m = (i+j)//2
if nums[m] < target:
i = m+1
elif nums[m] > target:
j = m
else:
j = m
return i

扩展 2:二分查找元素边界

查找左边界

等价于上述问题。

查找右边界

法1:寻找 target+1 的左边界索引再 -1

1
2
3
4
5
6
7
8
9
10
11
def binary_search_right_edge(nums: list[int], target: int) -> int:
"""二分查找最右一个 target"""
# 转化为查找最左一个 target + 1
i = binary_search_insertion(nums, target + 1)
# j 指向最右一个 target ,i 指向首个大于 target 的元素
j = i - 1
# 未找到 target ,返回 -1
if j == -1 or nums[j] != target:
return -1
# 找到 target ,返回索引 j
return j

法2:构造不存在元素查找

注意,此方法仅适用于 int 类型或选用更小精度的 float
当数组不包含 target 时,最终 i 和 j 会分别指向首个大于、小于 target 的元素。

1
2
3
4
5
6
7
8
9
10
def binary_search_new_ele(nums: list[int], target: int) -> tuple[int, int]:
# 左边界
i = binary_search_insertion(nums, target - 0.5)
# 右边界
j = binary_search_insertion(nums, target + 0.5)-1
if i == len(arr) or arr[i] != target:
i = -1
if j == -1 or arr[j] != target:
j = -1
return i, j