小结¶
左右边界找到后,先确认相等¶
在 [2, 4, 4, 6] 里找 5 的插入点,以及 4 的完整范围。检查二分给出的边界是否还在数组内,再决定能否当作查找命中。
两个查询的结果分别是什么?
5 的插入点为 3,指到值 6,因此 5 不存在。4 的范围是 [1, 3),共两项。
- 二分查找依赖数据的有序性,通过循环逐步缩减一半搜索区间来进行查找。它要求输入数据有序,且仅适用于数组或基于数组实现的数据结构。
- 暴力搜索通过遍历数据结构来定位数据。线性搜索适用于数组和链表,广度优先搜索和深度优先搜索适用于图和树。此类算法通用性好,无须对数据进行预处理,但时间复杂度 \(O(n)\) 较高。
- 哈希查找、树查找和二分查找属于高效搜索方法,可在特定数据结构中快速定位目标元素。此类算法效率高,时间复杂度可达 \(O(\log n)\) 甚至 \(O(1)\) ,但通常需要借助额外数据结构。
- 实际中,我们需要对数据体量、搜索性能要求、数据查询和更新频率等因素进行具体分析,从而选择合适的搜索方法。
- 线性搜索适用于小型或频繁更新的数据;二分查找适用于大型、排序的数据;哈希查找适用于对查询效率要求较高且无须范围查询的数据;树查找适用于需要维护顺序和支持范围查询的大型动态数据。
- 用哈希查找替换线性查找是一种常用的优化运行时间的策略,可将时间复杂度从 \(O(n)\) 降至 \(O(1)\) 。