Skip to main content

3.11 Binary Search

add to ChatGPT
Verified for the 2027 examUpdated September 2026Fiveable Content Team
Fiveable

⌨️AP Computer Science Principles Unit 3 Review

QR code for AP Computer Science Principles practice questions

3.11 Binary Search

What is binary search in AP Computer Science Principles?

Binary search is a way to find a value in a sorted data set by checking the middle, then throwing away the half that cannot contain the target, and repeating. It only works on sorted data, and because it eliminates half the remaining values each step, it is usually faster than checking items one at a time.

Binary search appears in AP Computer Science Principles as part of evaluating and comparing algorithms, so expect questions that ask which search is more efficient or whether a search can be used at all.

Binary Search Halves Sorted Data Each Step

  • Binary search starts in the middle of a sorted data set and removes half the remaining values each step until it finds the target or runs out of values.
  • The data must be sorted before you can use binary search. If it is not sorted, binary search will not work correctly.
  • Each step cuts the search space roughly in half, so binary search is often more efficient than linear search on sorted data.
  • Linear (sequential) search checks each element in order and works on any list, sorted or not.
  • You should be able to count how many times the data gets halved to reach a value, not write the actual code.
  • Specific implementations of binary search are outside what the exam asks you to do.

How Binary Search Works

Linear or sequential search checks each value of a list in order until the target is found or every element has been checked. It works on any list. Binary search is a different approach that only works on sorted data.

Binary search starts in the middle of a sorted data set and eliminates half of the data based on what it is looking for. It then repeats the process until the target value is found or until all values have been eliminated.

For example, say you have this sorted list and you want to find where 12 is:

1, 1, 2, 3, 3, 4, 5, 7, 9, 11, 12

Look at the middle value, which is 4.

1, 1, 2, 3, 3, 4, 5, 7, 9, 11, 12

Since 12 is greater than 4, the program ignores everything before and including 4. The remaining values are:

5, 7, 9, 11, 12

Look at the new middle value, which is 9.

5, 7, 9, 11, 12

Since 12 is greater than 9, the program ignores everything before and including 9. The remaining values are:

11, 12

This process keeps going until the program either finds 12 or has eliminated every value. Each step throws away about half of what is left, which is why so few checks are needed.

Why Sorting Matters

Data must be in sorted order to use binary search. The whole method depends on knowing that everything to the left of the middle is smaller and everything to the right is larger. If the data is not sorted, eliminating half the list could throw away the value you are looking for.

When the data is sorted, binary search is often more efficient than sequential search because it removes half the remaining data with every step instead of checking values one by one. That saves a lot of work on large data sets.

Tracing Binary Search and Checking Sorted Data

MCQ:

  • If a question gives you a sorted list and a target, trace the halving process: find the middle, decide which half to keep, and repeat. Count how many checks it takes.
  • If a question asks whether binary search can be used, check whether the data is sorted first. Unsorted data rules out binary search.
  • For efficiency comparisons, remember binary search usually beats linear search on sorted data because it eliminates half the values each step.

Common Trap:

  • A list must be sorted before binary search. Do not assume a random list is searchable with binary search.
  • Each step removes about half the remaining values, not a fixed number of values, so the number of checks grows slowly even when the list gets much bigger.

Common Misconceptions

  • Misconception: Binary search works on any list.
    Actually: It only works on sorted data. If the list is not sorted, the result is unreliable.
  • Misconception: Binary search always finds the value.
    Actually: It stops when the value is found or when all values have been eliminated. The target might not be in the list at all.
  • Misconception: You need to memorize the code.
    Actually: The exam does not ask you to write a specific binary search implementation. You need to understand the requirements and trace the halving process.
  • Misconception: Binary search is always faster than linear search.
    Actually: It is often more efficient on sorted data, but linear search works on any list and can be simpler for small or unsorted data.
  • Misconception: Each step removes one value.
    Actually: Each step eliminates about half of the values that are left, which is what makes it efficient.

Practice Questions for 3.11

1 of 10

A programmer implements a binary search to find a target value located at index 11 in a sorted list of 15 integers. The program draws a circle at (mid, 5) for each mid index checked during the search. The resulting drawing is shown above.

Which of the following errors in the code best explains this sequence of checks?

A.

The algorithm fails to stop when left > right.

B.

The algorithm updates the search bounds using mid instead of mid + 1 and mid - 1.

C.

The algorithm calculates the middle index using (left + right) / 2 without rounding.

D.

The condition determining which half of the list to search was reversed.

Vocabulary

The following words are mentioned explicitly in the AP® course framework for this topic.

Term

Definition

binary search algorithm

A search algorithm that starts at the middle of a sorted data set and eliminates half of the remaining data with each iteration until the desired value is found or all elements are eliminated.

iterations

The repeated cycles or steps of a process; in binary search, the number of times the algorithm divides the data set in half.

sequential search

A search algorithm that examines each element in a data set one by one in order until the desired value is found.

sorted data

Data arranged in a specific order (ascending or descending) that is required for binary search to function correctly.

See Fiveable more often in Google

Mark Fiveable as a preferred source and Google is more likely to show you our guides in Top Stories, with a "preferred" badge in AI Mode and AI Overviews.

Prefer us on Google