搜索分两大类
- 暴力搜索：它通过遍历数据结构实现，时间复杂度为 𝑂(𝑛) 。
- 自适应搜索：它利用特有的数据组织形式或先验信息，可达到 𝑂(log 𝑛) 甚至 𝑂(1) 的时间复杂度。
二分查找
二分查找 binary search：是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮减少一半搜索范围，直至找到目标元素或搜索区间为空为止。
由于𝑖 和 𝑗 都是 int 类型，因此 𝑖 + 𝑗 可能会超出 int 类型的取值范围。为了避免大数越界，我们通常采用公式𝑚 = ⌊𝑖 + (𝑗 − 𝑖)/2⌋来计算中点。
def binary_search(lst, val): i, j = 0, len(lst)-1 while i <= j: m = int(i + (j - i) / 2) if val > lst[m]: i = m+1 elif val < lst[m]: j = m-1 else: return lst[m] return -1
时间复杂度 𝑂(log𝑛) ：在二分循环中，区间每轮缩小一半，循环次数为 log2 𝑛 。
空间复杂度𝑂(1) ：指针𝑖 和 𝑗 使用常数大小空间。
二分查找的局限性
- 二分查找仅适用于有序数据。若输入数据无序，为了使用二分查找而专门进行排序，得不偿失。因为排序算法的时间复杂度通常为𝑂(𝑛 log 𝑛) ，比线性查找和二分查找都更高。对于频繁插入元素的场景，为保持数组有序性，需要将元素插入到特定位置，时间复杂度为𝑂(𝑛) ，也是非常昂贵的。
- 二分查找仅适用于数组。二分查找需要跳跃式（非连续地）访问元素，而在链表中执行跳跃式访问的效率较低，因此不适合应用在链表或基于链表实现的数据结构。
- 小数据量下，线性查找性能更佳。在线性查找中，每轮只需要 1 次判断操作；而在二分查找中，需要 1次加法、1 次除法、1 ~ 3 次判断操作、1 次加法（减法），共 4 ~ 6 个单元操作；因此，当数据量 𝑛 较小时，线性查找反而比二分查找更快。
二分查找插入(存在重复元素时)
def binary_search_insert(lst, val): lst = list(lst) i, j = 0, len(lst)-1 insert_ix = 0 while i <= j: m = int(i + (j -i)/2) if val > lst[m]: i = m + 1 elif val < lst[m]: j = m - 1 else: j = m - 1 # 可以将区间往第一个重复数据缩放 insert_ix = i lst.insert(insert_ix, val) return np.array(lst)
二分查找边界
查找边界
方法1
def binary_search_left_edge(lst, target): i, j = 0, len(lst) - 1 while i <= j: m = int(i + (j - i)/2) if target > lst[m]: i = m + 1 elif target < lst[m]: j = m - 1 else: j = m - 1 return i def binary_search_right_edge(lst, target): i, j = 0, len(lst) - 1 while i <= j: m = int(i + (j - i)/2) if target > lst[m]: i = m + 1 elif target < lst[m]: j = m - 1 else: i = m + 1 return j
方法2
def binary_search_right_edge(lst, target): ix = binary_search_left_edge(lst, target + 1) return ix - 1
哈希优化策略
Q:给定一个整数数组 nums 和一个目标元素 target ，请在数组中搜索“和”为 target 的两个元素，并返回它们的数组索引。返回任意一个解即可。
def hash_method(lst, target): print(lst, target) map = dict() for ix, item in enumerate(lst): target_key = target - item if target_key not in map.keys(): map[item] = ix else: return [ix, map[target_key]], [lst[ix], lst[map[target_key]]] return None
重识搜索算法
- 通过遍历数据结构来定位目标元素，例如数组、链表、树和图的遍历等。
- 利用数据组织结构或数据包含的先验信息，实现高效元素查找，例如二分查找、哈希查找和二叉搜索树查找等。
线性搜索
- 通用性较好，无须任何数据预处理操作。假如我们仅需查询一次数据，那么其他三种方法的数据预处理的时间比线性搜索的时间还要更长。
- 适用于体量较小的数据，此情况下时间复杂度对效率影响较小。
- 适用于数据更新频率较高的场景，因为该方法不需要对数据进行任何额外维护。
二分查找
- 适用于大数据量的情况，效率表现稳定，最差时间复杂度为 𝑂(log 𝑛) 。
- 数据量不能过大，因为存储数组需要连续的内存空间。
- 不适用于高频增删数据的场景，因为维护有序数组的开销较大。
哈希查找
- 适合对查询性能要求很高的场景，平均时间复杂度为 𝑂(1) 。
- 不适合需要有序数据或范围查找的场景，因为哈希表无法维护数据的有序性。
- 对哈希函数和哈希冲突处理策略的依赖性较高，具有较大的性能劣化风险。
- 不适合数据量过大的情况，因为哈希表需要额外空间来最大程度地减少冲突，从而提供良好的查询性能。
树查找
- 适用于海量数据，因为树节点在内存中是离散存储的。
- 适合需要维护有序数据或范围查找的场景。
- 在持续增删节点的过程中，二叉搜索树可能产生倾斜，时间复杂度劣化至𝑂(𝑛) 。
- 若使用 AVL 树或红黑树，则各项操作可在𝑂(log 𝑛) 效率下稳定运行，但维护树平衡的操作会增加额外开销
重点回顾
- 二分查找依赖于数据的有序性，通过循环逐步缩减一半搜索区间来实现查找。它要求输入数据有序，且仅适用于数组或基于数组实现的数据结构。
- 暴力搜索通过遍历数据结构来定位数据。线性搜索适用于数组和链表，广度优先搜索和深度优先搜索适用于图和树。此类算法通用性好，无须对数据预处理，但时间复杂度 𝑂(𝑛) 较高。
- 哈希查找、树查找和二分查找属于高效搜索方法，可在特定数据结构中快速定位目标元素。此类算法效率高，时间复杂度可达 𝑂(log 𝑛) 甚至 𝑂(1) ，但通常需要借助额外数据结构。
- 实际中，我们需要对数据体量、搜索性能要求、数据查询和更新频率等因素进行具体分析，从而选择合适的搜索方法。
- 线性搜索适用于小型或频繁更新的数据；二分查找适用于大型、排序的数据；哈希查找适合对查询效率要求较高且无须范围查询的数据；树查找适用于需要维护顺序和支持范围查询的大型动态数据。
- 用哈希查找替换线性查找是一种常用的优化运行时间的策略，可将时间复杂度从 𝑂(𝑛) 降低至 𝑂(1) 。
