3.11 Binary Search

Enduring Understanding

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.

Learning Objective

For binary search algorithms:

a. Determine the number of iterations required to find a value in a data set.

b. Explain the requirements necessary to complete a binary search.

Essential Knowledge

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

Exclusion Statement: Specific implementations of the binary search are outside the scope of the course and the AP Exam.

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

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