视频字幕
二分查找算法是计算机科学中的一种重要搜索算法。它专门用于在有序数组中快速查找目标元素。算法的核心思想是每次将搜索区间缩小一半，从而大大提高查找效率。与线性查找的O(n)时间复杂度相比，二分查找的时间复杂度仅为O(log n)，这使得它在处理大型数据集时具有显著优势。
二分查找算法的执行步骤非常清晰。首先，我们初始化搜索区间，设置low指针指向数组开始，high指针指向数组结束。然后计算中间位置mid。接下来比较目标值与中间元素的大小关系，根据比较结果缩小搜索区间。这个过程会重复进行，直到找到目标元素或搜索区间为空。
现在让我们通过一个具体例子来演示二分查找的执行过程。我们要在数组中查找目标值11。第一次比较：中间元素是9，小于目标值11，所以搜索右半部分。第二次比较：中间元素是15，大于目标值11，所以搜索左半部分。第三次比较：中间元素正好是11，找到目标值！
现在让我们看看C++中二分查找的具体代码实现。这是一个迭代版本的实现。首先初始化low和high指针，然后在while循环中不断缩小搜索区间。计算中间位置时使用low加上high减low除以2的方式，这样可以避免整数溢出。根据比较结果更新搜索区间，直到找到目标或搜索区间为空。该算法的时间复杂度是O(log n)，空间复杂度是O(1)。
总结一下今天学习的二分查找算法。二分查找是一种高效的搜索算法，专门用于有序数组。它的时间复杂度是O(log n)，比线性查找的O(n)效率高得多。算法的核心思想是每次将搜索区间缩小一半，通过不断比较中间元素与目标值来确定搜索方向。在C++中实现简洁明了，既可以用迭代方式也可以用递归方式。这个算法在算法竞赛和实际软件开发中都有广泛应用。