AP CSP
AP Computer Science Principles / All lessons / Big Idea 3: Algorithms and Programming
3Big Idea 3: Algorithms and Programming
AP CSP topic 3.11

Binary Search

A linear search checks each element one by one and works on any list. A binary search only works on a sorted list: it checks the middle element, then throws away the half that cannot contain the target, repeating until it finds the value or runs out. Each step cuts the list in half, so binary search is much faster on large lists. Searching 1,000 sorted items takes at most about 10 checks.

Picture it369121518212427303336394245483691215182124273033363942454836912151821242730333639424548
Binary search for 33 in a sorted list. Check the middle (27, too small) and keep the right half. Check 39 (too big) and keep the left. Check 33: found in 3 checks. A linear search would need 11.

Binary Search vocabulary

  • Linear search: Checking elements one at a time from the start until the target is found.
  • Binary search: Repeatedly checking the middle of a sorted list and discarding half.
  • Sorted: Arranged in order, such as smallest to largest.
  • Efficiency: A measure of how much work an algorithm does as the input grows.

AP-style practice questions

Try each one, then open the answer. To save your progress, take this quiz in the interactive course.

Skill: Algorithms and Program Development

1. Which of the following must be true before a binary search can be used on a list?

  1. (A) The list must have an even number of elements
  2. (B) The list must be sorted
  3. (C) The list must contain only strings
  4. (D) The list must have fewer than 100 elements
Show answer

(B) The list must be sorted Binary search relies on order to discard half of the list each step.

Skill: Code Analysis

2. About how many elements must a binary search check, in the worst case, to search a sorted list of 1,000 elements?

  1. (A) About 10
  2. (B) About 100
  3. (C) About 500
  4. (D) 1,000
Show answer

(A) About 10 Each step halves the list. 2^10 = 1,024, so about 10 checks.

Skill: Algorithms and Program Development

3. A list of 50 names is in random order. Which search method should be used to find one name?

  1. (A) Binary search, because it is faster
  2. (B) Linear search, because the list is not sorted
  3. (C) Neither, because searching is impossible
  4. (D) Binary search, because 50 is even
Show answer

(B) Linear search, because the list is not sorted Binary search needs a sorted list. Linear search works on any list.

Skill: Code Analysis 
Sorted list: [3, 8, 12, 19, 24, 31, 40]

4. A binary search looks for 31. Which element is checked first?

  1. (A) 3
  2. (B) 19
  3. (C) 31
  4. (D) 40
Show answer

(B) 19 Binary search starts with the middle element, which is 19.

Open 3.11 in the interactive course