视频字幕
欢迎了解二分查找算法。二分查找是一种在有序数组中查找特定元素的高效算法。它的核心思想是每次比较中间元素，将搜索范围缩小一半，直到找到目标或确定目标不存在。使用二分查找的前提条件是数组必须是有序的。与线性查找的O(n)时间复杂度相比，二分查找的时间复杂度为O(log n)，这使得它在处理大规模数据时特别高效。在这个例子中，我们有一个包含9个元素的有序数组，我们将要查找值为50的元素。
让我们详细了解二分查找的步骤。首先，我们初始化左指针low为0，右指针high为数组最后一个元素的索引8。然后，我们计算中间指针mid，即low加high除以2，得到4。接下来，我们比较中间元素array[4]，也就是50，与我们的目标值50。由于它们相等，我们成功找到了目标值，算法结束。如果目标值小于中间元素，我们会将搜索范围缩小到左半部分，更新high等于mid减1；如果目标值大于中间元素，我们会将搜索范围缩小到右半部分，更新low等于mid加1。这个过程会一直重复，直到找到目标值或者确定目标值不存在于数组中。
让我们通过一个具体例子来演示二分查找的过程。假设我们要在同一个有序数组中查找值70。在第一次迭代中，low为0，high为8，mid为4。我们比较array[4]，也就是50，与目标值70。由于50小于70，说明目标值在中间元素的右侧，所以我们更新low等于mid加1，即5。在第二次迭代中，low为5，high为8，mid为6。我们比较array[6]，也就是70，与目标值70。它们相等，说明我们找到了目标值，算法结束，返回索引6。通过这个例子，我们可以看到二分查找每次迭代都会将搜索范围缩小一半，这就是为什么它的时间复杂度是O(log n)的原因。
现在让我们看看二分查找的Python实现。这段代码展示了二分查找的基本结构。首先，我们初始化左指针low为0，右指针high为数组长度减1。然后，在一个while循环中，只要low小于等于high，我们就计算中间索引mid，并比较中间元素与目标值。如果相等，返回mid；如果中间元素小于目标值，更新low为mid加1；如果中间元素大于目标值，更新high为mid减1。如果循环结束后仍未找到目标值，返回-1表示目标不存在。接下来，让我们分析二分查找的复杂度。时间复杂度为O(log n)，因为每次迭代都将搜索范围缩小一半，对于长度为n的数组，最多需要log₂n次比较。空间复杂度为O(1)，因为只需要常数个变量。与线性查找的O(n)相比，二分查找在大规模数据上效率显著提高。例如，对于一个包含一百万个元素的数组，线性查找最多需要一百万次比较，而二分查找最多只需要20次比较。
让我们总结一下二分查找算法的要点。二分查找是一种在有序数组中查找特定元素的高效算法。它的核心思想是每次比较中间元素，将搜索范围缩小一半，直到找到目标或确定目标不存在。二分查找的时间复杂度为O(log n)，空间复杂度为O(1)。相比于线性查找的O(n)时间复杂度，二分查找在处理大规模数据时效率显著提高。二分查找广泛应用于数据库索引、字典查找、系统搜索等场景。然而，需要注意的是，二分查找的前提条件是数组必须是有序的，如果数组是无序的，需要先进行排序，这可能会增加额外的时间复杂度。总的来说，二分查找是一种简单而强大的算法，是计算机科学中的基础算法之一。