算法之二分查找算法
本文最后更新于 2024-12-09，文章内容可能已经过时。
Ⅰ、算法的概念
在计算机科学中，二分搜索（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
Ⅱ、算法思想
二分查找算法是一种高效的搜索算法，它基于分治策略，在有序数组中快速定位特定元素。该算法的核心思想是通过反复将待查区间减半来缩小搜索范围，从而大大减少查找所需的时间。具体来说，二分查找首先检查数组中间位置的元素是否为目标值；如果目标值更大，则在数组右半部分继续查找；如果更小，则在左半部分继续查找。这一过程不断重复，直到找到目标元素或确定其不存在于数组中。
为了确保二分查找的有效性，输入的数据必须满足两个条件：一是数据必须存储在一个支持随机访问的数据结构中，如数组；二是这些数据需要按照一定的顺序排列（通常是升序）。这是因为二分查找依赖于能够直接访问任意索引处的元素，并且利用了已排序数据的特点来高效地排除不可能包含目标值的部分。
在实现上，二分查找有两种主要形式——迭代和递归。迭代方法使用循环结构逐步调整左右边界以缩小搜索空间；而递归版本则是通过函数自身调用来实现同样的逻辑。无论哪种方式，关键点都在于正确地计算中间点以及根据比较结果更新边界指针的位置。例如，在java中，可以通过m = (i + j) >>> 1这样的语句来获得当前区间的中间位置，同时为了避免整数溢出的问题，有时会采用m = i + (j - i) / 2的形式。
此外，值得注意的是，尽管二分查找通常应用于寻找确切匹配的情况，但它也可以扩展用于处理近似匹配问题，比如查找第一个等于给定值的位置、最后一个等于给定值的位置等变体。对于这类问题，我们可能需要对标准的二分查找流程做出一些调整，以便准确地定位到所需的边界。
综上所述，二分查找不仅适用于简单的查找任务，而且可以作为构建其他复杂算法的基础组件之一。它的优势在于能够在对数时间内完成操作，这对于大规模数据集尤其重要。然而，由于它要求数据事先被排序，因此在实际应用时还需要考虑排序的成本以及其他可能更适合特定场景的数据结构或算法。
Ⅲ、算法实现
一、二分查找基础版
/**
*
* i, j, m 指针都可能是查找目标
* i > j 时表示区域内没有要找的了
* 每次改变 i, j 边界时, m 已经比较过不是目标, 因此分别 m+1 m-1
* 向左查找, 比较次数少, 向右查找, 比较次数多
*
*
* @param arr 待查找的升序数组
* @param target 待查找的目标值
* @return <p>找到则返回索引</p>
* <p>找不到返回 -1</p>
*/
public static int binarySearchBasic(int[] arr, int target) {
// 设置指针和初值
int i = 0, j = arr.length - 1;
// N 次 元素在最左边 N 次，元素在最右边 2*N 次
// i~j 范围内
while (i <= j) {
int m = (i + j) >>> 1;
// 目标在左边
if (target < arr[m]) {
j = m - 1;
// 目标在右边
} else if (arr[m] < target) {
i = m + 1;
} else {
// 找到了
return m;
}
}
return -1;
}
二、二分查找2
/**
*
* i, m 指针可能是查找目标
* j 指针不可能是查找目标
* i >= j 时表示区域内没有要找的了
* 改变 i 边界时, m 已经比较过不是目标, 因此需要 i=m+1
* 改变 j 边界时, m 已经比较过不是目标, 同时j 指针不可能是查找目标. 所以 j=m
*
* @param arr 待查找的升序数组
* @param target 待查找的目标值
* @return <p>找到则返回索引</p>
* <p>找不到返回 -1</p>
*/
public static int binarySearch2(int[] arr, int target) {
int i = 0, j = arr.length;
while (i < j) {
int m = (i + j) >>> 1;
if (target < arr[m]) {
j = m;
} else if (arr[m] < target) {
i = m + 1;
} else {
return m;
}
}
return -1;
}
三、二分查找平衡版
/**
*
* 不指望循环内通过 m 找出目标, 缩小区间直至剩 1 个, 剩下的这个可能就是要找的(通过 i)
* i 指针可能是查找目标
* j 指针不可能是查找目标
* 因为以上3点,当区域内还剩一个元素时, 表示为 j - i == 1
* 改变 i 边界时, m 可能就是目标, 同时因为 i 指针可能是查找目标. 所以有 i=m
* 改变 j 边界时, m 已经比较过不是目标, 同时因为 j 指针不可能是查找目标. 所以有 j=m
* 三分支改为二分支, 循环内比较次数减少
*
* @param arr 待查找的升序数组
* @param target 待查找的目标值
* @return <p>找到则返回索引</p>
* <p>找不到返回 -1</p>
*/
public static int binarySearchBalance(int[] arr, int target) {
int i = 0, j = arr.length;
// 范围内待查找的元素个数 > 1 时
while (1 < j - i) {
int m = (i + j) >>> 1;
// 目标在左边
if (target < arr[m]) {
j = m;
// 目标在 m 或右边
} else {
i = m;
}
}
return (target == arr[i]) ? i : -1;
}
四、二分查找Leftmost
/**
*
* @param arr 待查找的升序数组
* @param target 待查找的目标值
* @return <p>返回 大于或等于 target 的最靠左索引</p>
*/
public static int binarySearchLeftmost(int[] arr, int target) {
int i = 0, j = arr.length - 1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target <= arr[m]) {
j = m - 1;
} else {
i = m + 1;
}
}
return i;
}
五、二分查找Rightmost
/**
*
* @param arr 待查找的升序数组
* @param target 待查找的目标值
* @return <p>返回 ≤ target 的最靠右索引</p>
*/
public static int binarySearchRightmost(int[] arr, int target) {
int i = 0, j = arr.length - 1;
while (i <= j) {
int m = (i + j) >>> 1;
if (target < arr[m]) {
j = m - 1;
} else {
i = m + 1;
}
}
return i - 1;
}
Ⅳ、复杂度
一、时间复杂度
- 最坏情况：O(log n)
- 在最坏的情况下，二分查找需要将搜索空间减半直到只剩下最后一个元素。因此，对于大小为 n 的数组，大约需要进行 log₂(n) 次比较。
- 最好情况：O(1)
- 如果要查找的元素正好位于数组的中间位置，那么只需一次比较就可以找到目标元素。
- 平均情况：O(log n)
- 平均情况下，时间复杂度也是 O(log n)，因为通常情况下不会在第一次尝试就找到目标元素，也不会每次都走到最坏情况。
二、空间复杂度
- 迭代实现：O(1)
- 使用迭代方式实现的二分查找只需要常量级别的额外空间来存储几个变量（如起始和结束索引），所以空间复杂度为 O(1)。
- 递归实现：O(log n)
- 使用递归方式实现时，每次递归调用都会在调用栈上占用一些空间。由于二分查找最多需要递归 log₂(n) 层，所以递归实现的空间复杂度为 O(log n)。
Ⅴ、算法优点
- 效率高：二分查找的时间复杂度为O(log n)，其中n是数组中的元素数量。这意味着随着数组大小的增长，查找所需的时间增长非常缓慢，相较于线性查找（时间复杂度为O(n)）来说，效率显著提高。
- 适用范围广：只要数据已经排序，就可以使用二分查找算法。这在处理大量数据且需要频繁查找的场景中特别有用，例如数据库索引、文件系统中的查找等。
- 稳定性好：二分查找算法的性能不会受到数组初始排列顺序的影响，每次查找的时间复杂度都是O(log n)，确保了算法的一致性和可靠性。
- 无须额外空间：相较于需要借助额外空间的搜索算法（例如哈希查找），二分查找更加节省空间，因为它直接在原数组上进行查找，不需要额外的数据结构来保存中间结果。
- 比较次数少，查找速度快：平均性能优秀，经过一次比较即可将查找范围缩小一半，从而大大减少了查找所需的比较次数。
Ⅵ、算法缺点
- 要求数据有序：二分查找算法要求数据必须是有序的。如果数据未排序，则需要先对其进行排序操作，这可能会增加额外的计算开销。此外，对所有数据元素按大小排列是非常费事的操作。
- 只适用于静态数据集或可快速更新的数据集：二分查找算法在查找过程中不修改原数组，因此它特别适用于静态数据集或可以快速更新的数据集。对于频繁变化的数据集（如频繁插入或删除元素），每次变化后都可能需要重新排序或调整索引，这会降低二分查找的效率。
- 插入删除困难：由于二分查找依赖于数据的有序性，所以在频繁进行插入或删除操作的数据记录中使用不太划算，因为要维持数据的有序还需要额外的排序开销。
- 对内存敏感：二分查找依赖于数组的随机访问特性，因此在内存访问速度较慢的环境中（如使用磁盘作为存储介质时），二分查找的效率可能会受到影响。
- 数据量太大不适合：当数据量特别大时，比如达到GB级别，由于二分查找底层依赖的是数组，而数组需要一段连续的存储空间，此时可能不太适合使用二分查找。
- 空间复杂度相对较高：某些情况下，如需创建辅助数组来存储排序后的数据集，二分查找的空间复杂度会相对较高。
Ⅶ、适用场景
1. 有序数组中的元素查找
二分查找最直接的应用是在一个已经排序好的数组中查找特定元素的位置。如果目标值存在于数组中，那么该算法可以在对数时间内找到它；如果不存在，则返回一个指示未找到的结果。这种情况下，二分查找比线性搜索效率更高，特别是在处理大量数据时。
2. 数据库查询优化
当涉及到数据库操作时，特别是那些频繁执行读取操作但写入较少的情况，可以利用索引来实现类似于二分查找的功能。例如，在某些键值存储系统如Redis中，为了节省空间并提高检索速度，会使用有序数组结合二分查找来快速定位记录。
3. 搜索算法优化
对于一些需要进行精确匹配或范围查询的问题，比如IP地址段归属地查询等，可以通过预先构建一个有序列表，并在此基础上应用二分查找来进行高效搜索。这样不仅可以加快查询过程，而且能够减少内存占用。
4. 排序算法验证
在测试排序算法正确性的过程中，也可以采用二分查找作为辅助工具之一。通过检查排序后数组是否满足二分查找的前提条件（即元素按升序或降序排列），从而间接证明了排序结果的有效性。
5. 数值计算与逼近解法
除了传统的整数或字符串类型的查找外，二分查找还可以应用于浮点数或其他连续型数值的近似求解问题上。例如，在求解方程根或者寻找某个函数的最大最小值时，只要能定义好比较规则，就可以利用二分查找逐步缩小解的空间直至达到所需的精度水平。
6. 工程和科学研究领域
在工程设计及科学实验等领域内，经常遇到参数调整以获得最佳性能指标的任务。此时可以考虑使用二分查找策略来确定最优参数设置，尤其是在已知解空间边界且变化趋势单调的情形下尤为适用。
7. 资源分配
在资源调度问题中，当面对有限数量的资源而需合理分配给多个请求者时，也可以引入二分查找思想来帮助决定每个用户可以获得多少份额。这通常涉及到构造适当的代价函数，并通过迭代调整直到找到平衡点。
8. 静态数据集的一次排序多次查找
考虑到维持一个始终有序的数据集合成本较高，因此最适合采用二分查找的是那些插入删除频率很低，但查询次数非常多的数据集。一旦完成了初次排序工作之后，后续每次查找都能享受到O(log n)级别的高效性能增益。
综上所述，尽管二分查找有着诸多优点，但它并不是万能的解决方案。选择合适的场景至关重要，只有当待解决问题符合上述特性之一时，才应该优先考虑运用此方法。此外，还需注意实际编程实现过程中可能出现的各种边界情况和技术细节，确保算法能够稳定可靠地运行。
