已发布·持续改进
Algorithm
查找算法用于在数据中定位值或位置，涵盖线性查找、二分查找、lower_bound 与 upper_bound、二分答案以及哈希查找。
查找是在一组数据中找到目标值，或者找到某个条件第一次成立的位置。线性查找逐个比较元素，适用于任何数据；二分查找每一步都把有序区间缩小一半，即使有一百万个元素也只需大约 20 次比较。如果只需要精确匹配键，哈希表平均可以在常数时间内给出答案。
几乎每个程序都要查找数据，因此查找是最基础的算法之一。数据库索引、自动补全、日志分析和路由表都依赖它。二分查找也不只用于数组：只要一个是/否条件在某个范围内只改变一次，就可以直接对答案进行二分。这样，编程面试中的许多最优化问题都能写成简短而可靠的代码。
建议先亲手写出线性查找和闭区间的二分查找，再练习半开区间的 lower_bound 与 upper_bound 写法，直到边界处理变得自然。用小数组手动跟踪执行过程，用随机输入把自己的代码与 Python 的 bisect 模块对比验证，最后通过最优化问题练习二分答案和三分查找。
逐个比较元素，耗时 O(n)。不需要排序，在元素较少时往往是最快的选择。
每一步把有序区间缩小一半，在 O(log n) 时间内找到目标值。迭代实现只需要 O(1) 的额外空间。
返回第一个大于等于或严格大于目标值的位置。两者之差就是重复元素的个数，Python 的 bisect 模块同时提供了这两个函数。
参数搜索把“可行的最小值是多少”转化为是/否判定，然后在所有可能答案的范围内进行二分。
lower_bound 使用半开区间 [lo, hi)，返回第一个值大于等于 x 的下标。若中间值小于 x，就舍弃左半部分，否则舍弃右半部分。contains 利用这个下标判断值是否存在，最后一行确认结果与标准库中的 bisect.bisect_left 一致。
searching.py
from bisect import bisect_left
def lower_bound(a, x):
"""Return the first index i with a[i] >= x (len(a) if there is none)."""
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
def contains(a, x):
i = lower_bound(a, x)
return i < len(a) and a[i] == x
if __name__ == "__main__":
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(lower_bound(data, 23), contains(data, 23)) # 5 True
print(lower_bound(data, 24), contains(data, 24)) # 6 False
print(lower_bound(data, 24) == bisect_left(data, 24)) # True
python searching.py共六章，带你从安装一步步了解 查找 的核心概念。
在这里提问、分享经验，交流关于 查找 的看法。
还没有讨论。来发起第一个吧。
0 条评论
登录 · 登录后即可发表评论。
来发表第一条评论吧。