视频字幕
二分查找是一种在有序数组中查找特定元素的高效算法。它的核心思想是通过比较目标值与数组中间元素的大小，每次将搜索范围缩小一半。二分查找要求数组必须是有序的，它的时间复杂度为对数级，即O(log n)，这使得它特别适合在大型数据集中进行快速查找。在这个例子中，我们有一个包含9个元素的有序数组，我们将使用二分查找来寻找值为50的元素。
让我们详细了解二分查找的步骤。首先，我们初始化左指针指向数组的第一个元素，右指针指向最后一个元素。然后，我们计算中间位置，即左右指针的平均值。接着，我们比较中间元素与目标值。如果它们相等，我们就找到了目标值；如果目标值小于中间元素，我们将右指针移到中间位置的左侧；如果目标值大于中间元素，我们将左指针移到中间位置的右侧。在这个例子中，我们要查找值为70的元素。第一次迭代时，中间元素是50，而70大于50，所以我们将左指针移到中间位置的右侧，继续在右半部分查找。
在第二次迭代中，我们的左指针已经移动到索引5，右指针仍在索引8。我们重新计算中间位置，得到索引6。现在，我们比较中间元素70与目标值70。它们相等！这意味着我们已经找到了目标值，可以返回索引6作为结果。二分查找算法成功地在对数时间内找到了目标元素，而不需要遍历整个数组。这就是为什么二分查找在大型有序数据集上非常高效的原因。
让我们看看二分查找算法的Python实现。这个函数接受一个有序数组和一个目标值作为输入。它首先初始化左右指针，然后在循环中计算中间位置，并将目标值与中间元素进行比较。根据比较结果，它要么返回找到的索引，要么调整搜索范围。如果目标值不在数组中，函数返回-1。二分查找的时间复杂度是对数级的，即O(log n)，这意味着随着数组大小的增加，所需的比较次数只会略微增加。例如，对于一个包含一百万个元素的数组，线性搜索最多需要一百万次比较，而二分查找只需要大约20次比较就能找到目标值或确定它不存在。这种效率使得二分查找成为处理大型有序数据集的首选算法。