视频字幕
二分查找是一种高效的搜索算法，也称为折半查找。它的核心思想是每次比较中间元素，然后根据比较结果将搜索范围缩小到原来的一半。使用二分查找的前提条件是数组必须是有序的。让我们通过一个具体的例子来理解这个算法。
现在让我们详细了解二分查找的具体步骤。首先初始化搜索范围，设置low等于0，high等于9。然后计算中间索引mid等于low加high除以2，也就是4。接下来比较目标值13与中间元素arr[4]等于9。由于13大于9，我们知道目标值在右半部分，所以接下来要搜索右半部分。
让我们继续查找过程。第二轮查找中，low等于5，high等于9，mid等于7。arr[7]等于15大于13，所以搜索左半部分。第三轮查找中，low等于5，high等于6，mid等于5。arr[5]等于11小于13，所以搜索右半部分。第四轮查找中，low和high都等于6，mid等于6。arr[6]等于13正好等于目标值13，查找成功！我们只用了4次比较就找到了目标元素。
现在让我们看看二分查找的代码实现。算法的基本结构包括初始化low和high指针，然后在while循环中不断计算中间位置，比较中间元素与目标值，根据比较结果更新搜索范围。二分查找的时间复杂度是O(log n)，因为每次搜索范围都减半，最多需要log₂n次比较。空间复杂度是O(1)，只需要常数个变量。它的优点是效率高、速度快，适合大数据量查找，但缺点是要求数组必须有序，不适合频繁插入删除的场景。
总结一下我们学到的内容：二分查找是一种高效的搜索算法，时间复杂度为O(log n)。它的核心思想是每次将搜索范围缩小一半。使用二分查找的前提条件是数组必须有序排列。它特别适用于大数据量的静态查找场景。相比线性查找，二分查找在大数据集上有显著的性能优势。