Binary search is a searching algorithm for sorted arrays or lists that repeatedly compares the target to the middle element and discards half the remaining data each step, making it far faster than linear search but only valid when the data is already in order.
Binary search is the "guess the number" game turned into code. You're looking for a target value in a sorted array, so you check the middle element first. If the middle element equals the target, you're done. If the target is smaller, you throw away the entire right half. If it's larger, you throw away the left half. Then you repeat on whatever's left until you find the value or run out of elements to check.
The whole trick depends on one precondition. The data must be sorted. Sorting is what lets you safely discard half the array after one comparison, because you know everything on one side is too small and everything on the other is too big. In AP CSA you'll see binary search written two ways, as an iterative loop that adjusts low, high, and mid indices, and as a recursive method that calls itself on a smaller portion of the array. Both versions do the same thing, and you're expected to trace both.
Binary search sits at the heart of AP CSA's searching and sorting content. You first meet searching with linear (sequential) search on arrays and ArrayLists, then binary search shows up again in the recursion unit, where the recursive version is one of the two named recursive algorithms you have to know (merge sort is the other). The course also expects you to reason informally about efficiency by counting comparisons, and binary search is the classic example of why algorithm choice matters. Searching a million sorted elements takes at most about 20 comparisons with binary search, versus up to a million with linear search. That contrast between halving and one-at-a-time scanning is exactly the kind of reasoning multiple-choice questions reward.
Linear Search (Units 6-7)
Linear search checks every element one by one and works on any array, sorted or not. Binary search trades that flexibility for speed. The exam loves asking you to pick which search applies in a given situation, and the answer almost always hinges on whether the data is sorted.
Sorted Array/List (Unit 6)
Sorting is binary search's non-negotiable precondition. Given an unsorted array like {42, 17, 89, 56, ...}, you must sort it before binary search will work, because the halving logic assumes everything left of mid is smaller and everything right is larger.
Merge Sort (Unit 10)
Merge sort and recursive binary search are the two recursive algorithms named in AP CSA, and they share the same divide-and-conquer DNA. Merge sort splits the array in half to sort it; binary search splits the search range in half to find a value. Learn one and the other feels familiar.
Divide and Conquer (Unit 10)
Binary search is the cleanest example of this strategy. Each step shrinks the problem to half its previous size, which is why the number of comparisons grows so slowly. Doubling the array size adds only one more comparison in the worst case.
Binary search shows up mostly in multiple choice, and the questions test three things. First, the precondition. A question may hand you an unsorted array like {42, 17, 89, 56, 23, 71, 12, 63} and ask what must happen before binary search runs (sort it first). Second, tracing. You'll be given iterative or recursive binary search code and asked how many times the loop or method executes for a specific target, or which elements get compared along the way. Track low, high, and mid carefully, and remember mid uses integer division, so (low + high) / 2 truncates. Third, efficiency. Expect questions comparing the number of comparisons binary search needs versus linear search on the same data. For the recursive version, know the structure cold. The base case is an empty range (or a match), and the recursive call passes a smaller half of the array. On the FRQ side, binary search isn't a standard prompt, but recursion and array traversal logic absolutely are, so being able to write and trace it is good practice for both.
Linear search starts at index 0 and checks every element in order, so it works on any array and finds a target in at most n comparisons. Binary search jumps straight to the middle and halves the search space each step, needing only about log₂(n) comparisons, but it fails silently on unsorted data. It can skip right past the target because its assumptions about where values live are wrong. Quick gut check on the exam, if the array isn't sorted, binary search isn't an option.
Binary search only works on sorted data, and any AP question giving you an unsorted array is testing whether you know it must be sorted first.
Each comparison eliminates half of the remaining elements, so searching 1,000 elements takes at most about 10 comparisons instead of 1,000.
AP CSA expects you to trace both the iterative version (with low, high, and mid indices) and the recursive version (which calls itself on half the range).
The mid index is computed with integer division, so (low + high) / 2 truncates, and getting this wrong is a common trace error.
The recursive version's base cases are finding the target or having the low index pass the high index, which means the value isn't there.
Binary search and merge sort are the two recursive algorithms named in the AP CSA course, and both use a divide-and-conquer approach.
It's a searching technique for sorted arrays that compares the target to the middle element and eliminates half the remaining data each step, repeating until it finds the value or the search range is empty. AP CSA tests both an iterative version using low/high/mid indices and a recursive version.
No. Binary search's halving logic assumes everything left of the middle is smaller and everything right is larger, which is only true if the data is sorted. On an unsorted array it can skip past the target and wrongly report it missing, so you must sort first.
Linear search checks elements one by one from index 0 and works on any array, taking up to n comparisons. Binary search requires sorted data but halves the search space each step, taking only about log₂(n) comparisons, roughly 20 for a million elements versus up to a million for linear search.
Yes. Recursive binary search is one of the two named recursive algorithms in the course (merge sort is the other), and you should be able to trace it, identify its base cases, and explain how each recursive call works on half the previous range.
Roughly log₂(n) rounded up, plus one. For an array of 8 elements that's about 4 comparisons, and for 1,000 elements it's about 10. AP CSA frames this informally as counting comparisons rather than using Big-O notation.