二分搜索算法

二分查找是一种基础的查找算法，用于在已排序的数组或列表中高效地定位目标值。它遵循分治的原则，因此对于大型数据集而言非常高效。二分查找通过反复将搜索空间减半来操作，直到找到目标值或确定其不存在，从而缩小目标值可能位置的范围。

算法首先检查已排序数组的中间元素。如果中间元素与目标值匹配，则搜索成功，算法返回该元素的索引。如果目标值小于中间元素，算法将递归地在数组的下半部分重复搜索过程。反之，如果目标值大于中间元素，算法则搜索数组的上半部分。这个将搜索空间减半并选择适当的一半进行进一步探索的过程将一直持续，直到找到目标值或搜索空间变为空。

二分查找的历史

在计算机科学领域，二分查找是一项基础算法，它彻底改变了我们搜索和检索信息的方式。它是一种强大而优雅的技术，可以有效地在已排序的数组中定位目标值。要真正欣赏它的重要性，我们必须深入了解二分查找引人入胜的历史，追溯其起源于古代。

二分查找的概念可以追溯到古代数学家和学者的工作。在已排序列表中搜索特定值的思想几个世纪以来一直吸引着知识分子。伟大的古希腊数学家欧几里得经常被认为是公元前三世纪最早提出二分查找算法版本的人。欧几里得的算法被称为“穷竭法”，它通过迭代地将一个范围减半直到找到所需的值。

快进到 20 世纪中叶，二分查找算法在新兴的计算机科学领域开始获得关注。正是在这个时候，约翰·莫奇利和 J. Presper Eckert 等先驱为电子数字计算机奠定了基础。随着计算机的普及，对高效搜索算法的需求变得越来越明显。

1946 年，宾夕法尼亚大学摩尔电气工程学院取得了突破性进展。ENIAC，世界上第一批通用电子计算机之一，被推出。ENIAC 为计算研究开辟了新途径，包括探索更复杂的搜索算法。

正是在这种背景下，二分查找被引入数字计算领域。1946 年标志着一个重要的里程碑，约翰·W·莫奇利和威廉·S·伯勒斯发表了一篇开创性论文。在他们的论文中，他们描述了一种专门为电子数字计算机量身定制的二分查找算法，该算法利用了二进制算术和迭代减半的力量来有效地定位所需值。

随后的几十年里，二分查找算法得到了稳步改进。来自世界各地的计算机科学家和研究人员寻求提高其效率并将其应用于各种应用。1962 年，计算机科学领域的杰出人物唐纳德·克努斯 (Donald Knuth) 提出了一种至今仍被广泛使用的二分查找算法。克努斯的算法被称为带中间元素的二分查找，它采用了更优雅的方法，消除了不必要的计算，并进一步优化了搜索过程。

20 世纪后期，高级编程语言的出现和计算平台的普及推动了二分查找的更广泛应用。它成为计算机编程中的一项基本工具，使开发人员能够高效地在海量数据中进行搜索，而所需时间仅为以前的零头。

总之，二分查找的历史证明了对高效算法的不懈追求。从古代数学家的早期概念化到其集成到数字领域，二分查找在几个世纪中不断发展和成熟。它在现代计算中持续的相关性和广泛采用，证明了其优雅和有效性。随着我们进入一个日益数据驱动的世界，二分查找的遗产无疑将继续塑造我们有效导航和检索信息的方式。

二分查找的效率在于其每次迭代都能消除大部分数据集。通过在每一步将搜索空间减半，该算法可以快速缩小目标值可能位置的范围。这导致时间复杂度为 O(log n)，其中 n 表示数组的大小。对数时间复杂度意味着二分查找即使对于海量数据集也能高效处理，因为所需的比较次数会随着输入的大小呈对数增长。需要注意的是，二分查找要求输入数组在初始时是已排序的。如果数组未排序，算法可能会产生错误的结果。此外，二分查找假定可以随机访问数组元素，这意味着访问中间元素可以在常数时间内完成。这个假设通常在基于数组的数据结构中满足。

在数据结构中应用二分查找的条件

应用二分查找算法

• 数据结构必须已排序。
• 访问数据结构的任何元素都需要常数时间。

二分查找算法

• 将搜索空间的中间元素与键进行比较。
• 如果键在中间元素处找到，则终止该过程。
• 如果键在中间元素处未找到，请选择哪个半部分将用作下一个搜索空间。
• 如果键小于中间元素，则左侧用于下一次搜索。
• 如果键大于中间元素，则右侧用于下一次搜索。
• 此过程将继续进行，直到找到键或耗尽整个搜索空间。

二分查找如何工作？

要理解二分查找的工作原理，请考虑以下说明

考虑一个数组 arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}，目标值为 23。

第一步：计算中间值，并将中间元素与键进行比较。如果键小于中间元素，则移至左侧；如果键大于中间元素，则将搜索空间移至右侧。

• 键（即 23）大于当前中间元素（即 16）。搜索空间移至右侧。
  
• 键小于当前中间值 56。搜索空间移至左侧。
  

第二步：如果键与中间元素的值匹配，则找到该元素并停止搜索。

如何实现二分查找？

二分查找算法可以通过以下两种方式实现

• 迭代二分查找算法
• 递归二分查找算法

下面是这两种方法的伪代码。

1. 迭代二分查找算法：

在这里，我们使用一个 while 循环来继续比较键并将搜索空间分成两个部分的过程。

下面是 C++ 代码的示例

输出

Element is present at index 3
Process executed in 1.11 seconds
Press any key to continue.

时间复杂度：O(log N)

辅助空间：O(1)

2. 递归二分查找算法

创建一个递归函数，将键的中间值与搜索空间的中间值进行比较。根据结果，要么为下一个搜索空间调用递归过程，要么返回找到键的索引。

下面是 C++ 程序示例

输出

Element is present at index 3
Process executed in 1.11 seconds
Press any key to continue.

时间复杂度

最佳情况：O(1)

平均情况：O(log N)

最坏情况：O(log N)

辅助空间：O(1)，如果考虑递归调用堆栈，则辅助空间为 O(logN)。

二分查找的复杂度分析

二分查找算法的最佳情况时间复杂度：O(1)

元素位于数组的中间索引是理想情况。只需一次比较即可找到目标元素。因此，最佳情况复杂度为 O(1)。

二分查找算法的平均情况时间复杂度：O(log N)

二分查找算法的最坏情况时间复杂度：O(log N)

最坏情况发生在元素位于第一个位置时。如平均情况所示，到达第一个元素所需的比较次数为 logN。因此，最坏情况的时间复杂度为 O(logN)。

二分查找算法的辅助空间复杂度

二分查找算法在搜索元素时不需要额外的空间。因此，其辅助空间复杂度为 O(1)

二分查找的优点

• 特别是对于大型数组，二分查找比线性查找更快。
• 与具有相似时间复杂度的其他搜索算法（如指数搜索或插值搜索）相比，效率更高。
• 最好通过二分查找来搜索存储在外部内存（如硬盘或云）中的大型数据集。

二分查找的缺点

• 需要对数组进行排序。
• 为了使用二分查找，必须将要搜索的数据结构保存在连续内存区域的集合中。
• 为了使二分查找能够工作，数组中的项必须是相似的，这意味着它们必须能够被排序。

二分查找的应用

• 对于更复杂的机器学习算法，例如用于训练神经网络或确定模型理想超参数的算法，二分查找可用作基础。
• 可用于查找与计算机图形学相关的术语，如光线追踪或纹理映射算法。
• 可应用于数据库搜索。