3.11 Binary Search 二分搜索

The way statements are sequenced and combined in a program determines the computed result. Programs incorporate iteration and selection constructs to represent repetition and make decisions to handle varied input values.

• 程序中语句的排序和组合方式决定了计算结果。程序结合迭代和选择结构来表示重复并做出决策来处理各种输入值。

核心要点 Core Points

1. The binary search algorithm starts at the middle of a sorted data set of numbers and eliminates half of the data; this process repeats until the desired value is found or all elements have been eliminated.

   • 二分搜索算法从排序数字数据集的中间开始，消除一半的数据；这个过程重复，直到找到所需值或所有元素都被消除。

2. Data must be in sorted order to use the binary search algorithm.

   • 数据必须按排序顺序才能使用二分搜索算法。

3. Binary search is often more efficient than sequential/linear search when applied to sorted data.

   • 当应用于排序数据时，二分搜索通常比顺序/线性搜索更高效。

学生活动 Student Activities

1. For binary search algorithms:
   • 对于二分搜索算法：
   • Determine the number of iterations required to find a value in a data set.
     • 确定在数据集中找到值所需的迭代次数。
   • Explain the requirements necessary to complete a binary search.
     • 解释完成二分搜索所需的要求。

相关资源 Related Resources

• Binary Search from College Board

  • 二分搜索 来自大学理事会

• Searching Algorithms from CS Unplugged

  • 搜索算法 来自CS Unplugged

》二分查找教学视频

算法原理

二分搜索是一种分治算法，通过反复将搜索空间一分为二，高效地在有序数组中定位目标值。

关键思想是：如果目标值不在中间位置，我们可以根据目标值是大于还是小于中间值来排除一半的剩余元素。

算法步骤

1. 初始化指针：设置 left = 0 和 right = array.length - 1

2. 计算中间值：mid = (left + right) / 2（整数除法使用 //）

3. 比较：

   • 如果 array[mid] == target：返回 mid（找到了！）
   • 如果 array[mid] < target：设置 left = mid + 1（搜索右半部分）
   • 如果 array[mid] > target：设置 right = mid - 1（搜索左半部分）

4. 重复：继续步骤 2-3，直到 left > right（未找到目标）

示例演示

示例：在有序数组 [1, 3, 5, 7, 9, 11, 13] 中搜索值 7

步骤 1：

• 数组：[1, 3, 5, 7, 9, 11, 13]
• 索引： 0 1 2 3 4 5 6
• left = 0，right = 6，mid = 3
• array[3] = 7 → 找到！返回索引 3

示例：在有序数组 [1, 3, 5, 7, 9, 11, 13] 中搜索值 6

步骤 1：

• left = 0，right = 6，mid = 3
• array[3] = 7 > 6 → 搜索左半部分，设置 right = 2

步骤 2：

• left = 0，right = 2，mid = 1
• array[1] = 3 < 6 → 搜索右半部分，设置 left = 2

步骤 3：

• left = 2，right = 2，mid = 2
• array[2] = 5 < 6 → 搜索右半部分，设置 left = 3

步骤 4：

• left = 3，right = 2 → left > right → 未找到，返回 -1

时间复杂度分析

• 最佳情况：O(1) - 目标值在中间位置
• 平均情况：O(log n) - 经过 log₂(n) 次比较后找到目标值
• 最坏情况：O(log n) - 未找到目标值或目标值在边缘位置

注意事项

1. 前提条件：应用二分搜索前，数组必须已排序

2. 与线性搜索的比较：二分搜索对于大型数据集更快，但需要有序数据