二分查找
基本知识
当数据量很大适宜采用二分查找方法。
采用二分法查找时，一般来说数据需是排好序的. 其实二分查找的核心是单调, 这个数组有序这是单调的一种情况, 对于局部调单也可以使用二分查找
基本思想：假设数据是按升序排序的，对于给定值key，从序列的中间位置k开始比较，
如果arr[k]=key，则查找成功
若key < arr[k]，则在数列的前半段中查找 (arr[low,mid-1])
若key > arr[k]，则在数列的后半段中继续查找 (arr[mid+1,high])
根据以上步骤, 我们可以得到其时间复杂度为O(log(n))
mid的确定位置, 有三种写法
mid = (l + r) / 2, 单l+r时,可能会因为数太大了而溢出mid = l + (r - l) / 2, 不会溢出mid = 1 + ((r - l) >> 2), 2法使用右移一位, 比除2快
跳出循环的条件
这是二分查找的难点!!
一般来说, 跳出循环的条件有两个: low < high和low <= high
按照条件有下图的情况:
根据这些情况, 需要根据问题, 进行具体分析
一般来说, 要返回mid的话, 边界条件为low < high, 否则为low <= high, 当然一些问题仍然需要自己根据题目的要求进行分析
算法题
有序数组中找到num
问题: 在一个有序数组中, 找某个数是否存在
这是最简单的二分法的算法题了
from typing import List
def find_num(lst: List[int], num: int) -> bool:
low = 0
high = len(lst) - 1
while low <= high:
mid = low + (high - low) >> 1
if num > lst[mid]:
low = mid + 1
elif num < lst[mid]:
high = mid - 1
else:
return True
return False
print(find_num([1, 2, 3, 4], 0))
print(find_num([1, 2, 3, 4], 1))
有序数组中找到>=num最左的位置
问题: 在一个有序数组中, 找>=某个数的最左的位置
如: [1, 1, 2, 2, 2, 2, 2, 2, 3]中大于等于2的数字的最左位置
题解
判断[1, 1, 2, 2, 2, 2, 2, 2, 3]
low = 0 high = 8的mid为4
由于lst[3] = 4 < 2, 所以high = mid - 1 = 3即 从[1, 1, 2, 2]中继续判断
low = 0 high = 3的mid为1
由于lst[1] = 1 > 2, 所以low = mid + 1 = 2, 即 从 [2, 2]中继续判断
low = 2 high = 3的mid为2
由于lst[2] = 2 >= 2, 所以high = mid - 1 = 1, 由于 low > high, 跳出循环
返回low, 即右边的那个数
代码
from typing import List
def find_left(lst: List, num: int) -> int:
low = 0
high = len(lst) - 1
while low <= high:
mid = int((low + high) / 2)
if lst[mid] >= num:
# >= num 时满足条件
# 但不知道前面是否还满足, 所以需要继续判断
high = mid - 1
else:
# 不满足条件
# 修改左区间
low = mid + 1
return low
print(find_left([1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4], 3)) # 8
print(find_left([1, 1, 2, 2, 2, 2, 2, 2, 3], 2)) # 2
有序数组中找到<=num最右的位置
问题: 在一个有序数组中, 找<=某个数的最右的位置
同样与上面的问题一样, 只不过把判断条件换了
代码:
from typing import List
def find_right(lst: List[int], num: int) -> int:
low = 0
high = len(lst) - 1
while low <= high:
mid = int((low + high) / 2)
if lst[mid] <= num:
low = mid + 1
else:
high = mid - 1
return high
print(find_right([1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4], 3)) # 17
print(find_right([1, 1, 2, 2, 2, 2, 2, 2, 3], 2)) # 7
局部最小值问题
什么是局部最小值?
arr[0] < arr[1]，0位置是局部最小arr[N-1] < arr[N-2]，N-1位置是局部最小arr[i-1] > arr[i] < arr[i+1]，i位置是局部最小
问题
给定一个数组arr，已知任何两个相邻的数都不相等，找到随便一个局部最小位置返回
在Leetcode上有一道类似的题目, 不过求的是局部最大值, 见: 山脉数组的峰顶索引, 其题解见: 山脉数组的峰顶索引的题解
题解
一般来说, 解题的方向有两个:
- 数据状况
- 问题标准
这个问题相邻两个数不相等, 且求的是局部最小值, 所以可以用二分查找的方式
第一步: 比较0位置和1位置的值, 判断0位置的值是否为局部最小的值, 是则返回
第二步: 比较N-1位置和N-2位置的值, 判断N-1位置的值是否为局部最小的值, 是则返回
假如不是0和N-1位置均不是局部最小值, 那么 1 到 N-2 范围内无论如何必然存在局部最小值, 如下图表示:
假如使用二分查找的方法, 每次去中间的值mid
判断mid是否为局部最小值, 是则返回
否则, 比mid小的一边必然存在局部最小值, 以此类推, 如下图:
代码
from typing import List
def find_min(lst: List[int]) -> int:
"""
寻找局部最小值
"""
lst_len = len(lst)
if lst_len <= 1 or lst[0] < lst[1]:
return 0
if lst[lst_len - 1] < lst[lst_len - 2]:
return lst_len - 1
# 正式处理中间
mid = 0
low = 0
high = lst_len - 1
while low < high:
mid = low + (high - low) // 2
if lst[mid - 1] > lst[mid] and lst[mid] < lst[mid + 1]:
return mid
# 取比当前数小的那边
if lst[mid - 1] < lst[mid]:
high = mid
else:
low = mid
return mid
print(find_min([1, 2, 7, 8, 9])) # 0
print(find_min([9, 8, 7, 5, 3])) # 4
print(find_min([10, 2, 7, 8, 9])) # 1
print(find_min([10, 9, 2, 8, 11])) # 2
print(find_min([10, 9, 8, 7, 11])) # 3
print(find_min([1, 2, 7, 8, 9, 10])) # 0
print(find_min([9, 8, 7, 5, 3, 2])) # 5
print(find_min([10, 2, 7, 8, 9, 11])) # 1
print(find_min([10, 9, 2, 8, 11, 12])) # 2
print(find_min([10, 9, 8, 7, 11, 13])) # 3
print(find_min([10, 9, 8, 7, 4, 13])) # 4
