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