视频字幕
二分查找是计算机科学中最重要的搜索算法之一。它专门用于在已排序的数组中查找特定元素。算法的核心思想是通过比较中间元素与目标值,每次将搜索范围缩小一半,从而实现对数时间复杂度。这里展示的是C++实现的标准二分查找代码。
现在我们开始演示二分查找的具体过程。我们有一个已排序的数组,包含10个元素,从2到91。我们要查找的目标值是23。初始状态下,low指针指向索引0,high指针指向索引9,搜索范围覆盖整个数组。接下来我们将逐步缩小搜索范围。
现在开始第一次迭代。首先计算中间位置:mid等于low加上high减去low的一半,即0加上9减0除以2,结果是4。数组第4个位置的值是16。我们比较16和目标值23,发现16小于23,说明目标值在右半部分。因此我们更新low为mid加1,即5,并将左半部分标记为已排除的搜索区域。
继续第二次迭代。现在搜索范围是索引5到9。计算新的中间位置:mid等于7,对应值56。比较56大于23,所以目标在左半部分,更新high为6。第三次迭代:mid等于5,对应值正好是23。比较结果23等于23,完全匹配!我们成功找到了目标值,返回索引5。二分查找算法高效地在3步内找到了目标。
总结二分查找算法的特点和优势。二分查找的时间复杂度是O(log n),空间复杂度是O(1),但要求数组必须已排序。与线性查找的O(n)复杂度相比,二分查找在处理大数据集时优势明显。例如对于1000个元素,线性查找最坏需要1000次比较,而二分查找最多只需要10次。这使得二分查找成为处理大规模有序数据的理想选择。