【算法】二分查找模板
基本使用
下面是二分查找的最基本形式, 其原理是通过判断中间元素与目标值的大小来确定搜索方向的, 这种方法不需要后处理, 因为该方法在搜索目标元素的时候会不断向两侧偏移, 倘若找不到目标元素, 索引会偏移到数组末尾.
基本特征
- 初始条件：
left = 0, right = length-1 - 终止：
left > right - 向左查找：
right = mid-1 - 向右查找：
left = mid+1
模板代码
def binarySearch(arr: List[int], target: int) -> int:
lo,hi = 0,len(arr)-1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] > target:
lo = mid + 1
elif arr[mid] < target:
hi = mid - 1
else:
return mid
return -1 # 这种方法能够遍历所有元素, 当越界则说明找不到
查找左右边界
查找左右边界的模板适用于存在多个符合条件的数, 并要求找到索引最大/最小的情况. 对于出现重复的情况, 需要将边界值设置为中间值, 以不断逼近目标.
基本特征
注意, 在查找右边界过程中, 是通过mid不断向右偏移来查找右端点的, 因此需要取
m
i
d
=
1
+
⌊
l
e
f
t
+
r
i
g
h
t
2
⌋
mid=1 + lfloor frac{left+right}{2}rfloor
mid=1+⌊2left+right⌋; 而在查找左端点的场景中, 是通过mid不断向左偏移来查找左端点的, 因此需要取
m
i
d
=
⌊
l
e
f
t
+
r
i
g
h
t
2
⌋
mid=lfloor frac{left+right}{2}rfloor
mid=⌊2left+right⌋
查找左边界
- 初始条件：
left = 0, right = length-1 - 中间值:
mid = (left + right) / 2 - 终止：
left == right - 向左查找：
right = mid - 向右查找：
left = mid+1
查找右边界
- 初始条件：
left = 0, right = length-1 - 中间值:
mid = 1 + (left + right) / 2 - 终止：
left == right - 向左查找：
right = mid - 1 - 向右查找：
left = mid
模板代码
def leftBinarySearch(arr: List[int], target: int) -> int:
if not arr:
return -1
lo, hi = 0, len(arr)-1
while lo < hi:
mid = (lo+hi)//2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return hi if arr[hi] == target else -1
def rightBinarySearch(arr: List[int], target: int) -> int:
if not arr:
return -1
lo, hi = 0, len(arr)-1
while lo < hi:
mid = (lo + hi) // 2 + 1
if arr[mid] > target:
hi = mid - 1
else:
lo = mid
return lo if arr[lo] == target else -1
查找最接近的值
在二分查找过程中, 可能有目标值不在数组中的情况发生, 在这个过程, 我们只需要找到一个值i满足
寻找左边界:
∃
i
s
.
t
∀
x
∈
a
r
r
[
i
:
]
x
≥
t
a
r
g
e
t
∧
∀
x
∈
a
r
r
[
:
i
]
,
x
<
t
a
r
g
e
t
寻找右边界:
∃
i
s
.
t
∀
x
∈
a
r
r
[
:
i
]
x
≤
t
a
r
g
e
t
∧
∀
x
∈
a
r
r
[
i
:
]
,
x
>
t
a
r
g
e
t
text{寻找左边界: } \ exists i s.tquadforall xin arr[i:] x ge target \ land forall xin arr[:i], xlt target \ text{寻找右边界: } \ exists i s.tquadforall xin arr[:i] x le target \ land forall xin arr[i:], xgt target
寻找左边界: ∃i s.t∀x∈arr[i:] x≥target∧∀x∈arr[:i], x<target寻找右边界: ∃i s.t∀x∈arr[:i] x≤target∧∀x∈arr[i:], x>target
基本特征
找左侧最接近的值
- 初始条件：
left = 0, right = length - 终止：
left == right - 向左查找：
right = mid - 1 - 向右查找：
left = mid
找右侧最接近的值
- 初始条件：
left = 0, right = length - 终止：
left == right - 向左查找：
right = mid - 向右查找：
left = mid+1
模板代码
def leftBisect(arr: List[int], target: int):
lo, hi = 0, len(arr)
while lo < hi:
mid = (lo+hi)//2
if arr[mid] < target:
lo = mid+1
else:
hi = mid
return lo
def rightBisect(arr: List[int], target: int):
lo, hi = 0, len(arr)
while lo < hi:
mid = (lo+hi)//2
if target < arr[mid]:
hi = mid
else:
lo = mid+1
return lo