The most common way of traversing a list is to go through each item in order, one at a time. This is also the most basic way to search through a list. This search method is called a linear or sequential search algorithm, and it checks each value of a list in order until the result is found.
However, this isn't the only way you can search through a list. You can also look through a list using a binary search.
The binary search algorithm starts in the middle of a sorted data set and eliminates half of the data based on what it's looking for. It then repeats the process until the desired value is found or until the algorithm has exhausted all the values in the list.
Traversing a List
For example, let's say you had a list that looked like this:
1, 1, 2, 3, 3, 4, 5, 7, 9, 11, 12
and you wanted to find where 12 was.
If you were doing a binary search, you would divide the list in half and look at the value there, which would be 4.
1, 1, 2, 3, 3, 4, 5, 7, 9, 11, 12
12 is greater than 4, so the program knows to disregard everything before and including that value.
1, 1, 2, 3, 3, 4, 5, 7, 9, 11, 12
The program would then divide the list into half again...
5, 7, 9, 11, 12
and look at the value 9. 9 is less than 12, so the program would eliminate everything before and including that value.
5, 7, 9, 11, 12
This process would go on until the program either found 12 or went through all the values in the list.
Data must first be sorted in order to use a binary search method. However, when used on sorted data, a binary search is often more efficient than a sequential search because it eliminates half the data with each round of splitting. This means that it doesn't have to evaluate many of the results, saving time that the program would usually spend going down the list in a sequential sort. Due to this, the binary search method is commonly used in modern programs.
🔗 Check out this video explaining binary searches, as well as ways they can be written out. To see a binary search algorithm written in Python, go here. (Don't worry, you won't need to know how the algorithm works for the test.)
Frequently Asked Questions
How do I write a binary search algorithm in Java?
Binary search requires a sorted array, a lower and upper bound, and repeatedly checks the midpoint to halve the search interval until it finds the value or the interval is empty (EK AAP-2.P.1–2). Note: the CED says specific implementations are outside exam scope, but you should be able to explain the process and iteration count (≈ ceil(log2 n) steps). Java example (iterative, avoids off-by-one): ```java public static int binarySearch(int[] a, int target) { int low = 0, high = a.length - 1; while (low <= high) { int mid = low + (high - low) / 2; // avoids overflow if (a[mid] == target) return mid; // found else if (a[mid] < target) low = mid + 1; else high = mid - 1; } return -1; // not found } ``` This runs in logarithmic time, halving the interval each iteration (EK AAP-2.P.3). For more topic review see the Binary Search study guide (https://library.fiveable.me/ap-computer-science-principles/unit-3/binary-search/study-guide/YADShVFQZbqwGicqH3ub) and thousands of practice problems (https://library.fiveable.me/practice/ap-computer-science-principles).
What's the difference between binary search and linear search?
Binary search and linear (sequential) search differ in how they look through data and how efficient they are. Linear search checks each element one-by-one from start to finish—it needs up to n comparisons in a list of n items (O(n)). Binary search requires the data to be sorted and starts at the midpoint, comparing the target to the middle value and eliminating half the remaining items each step; it takes about log2(n) iterations in the worst case (O(log n)). So for a sorted list of 1,024 items, binary search needs at most ~10 comparisons; linear search might need up to 1,024. Remember the AP CED requirements: data must be sorted for binary search (EK AAP-2.P.2) and you should be able to determine iteration counts (LO AAP-2.P.a). For a quick review, check the Topic 3.11 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-3/binary-search/study-guide/YADShVFQZbqwGicqH3ub) and practice problems (https://library.fiveable.me/practice/ap-computer-science-principles).
Why does my binary search keep giving me the wrong answer?
Usually it’s a small implementation bug, not the algorithm. Check these common causes (matches CED keywords like sorted data, midpoint, lower/upper bound, off-by-one): - Data not sorted: binary search only works on sorted data (EK AAP-2.P.2). If your input isn’t sorted, results will be wrong. - Midpoint calculation: use mid = low + (high - low) // 2 to avoid overflow and be consistent about floor vs ceil. - Off-by-one when updating bounds: after comparing to mid value, do low = mid + 1 or high = mid - 1 (not mid) unless you handle mid specially. Using mid instead of mid ± 1 often causes infinite loops or missed elements. - Wrong loop/termination condition: make sure your loop invariant covers all indices (e.g., while low <= high) and you check equality at the right time. - Mixing indices and values: compare the search value to array[mid], not to mid. - Duplicates: decide whether you need first/last occurrence; plain binary search may return any matching index. If you want step-by-step debugging examples and practice, see the AP binary search study guide (https://library.fiveable.me/ap-computer-science-principles/unit-3/binary-search/study-guide/YADShVFQZbqwGicqH3ub) and try problems at (https://library.fiveable.me/practice/ap-computer-science-principles).
I don't understand how binary search eliminates half the data each time - can someone explain?
Binary search cuts the list in half because each check rules out one entire half. You start with a sorted list and pick the midpoint. Compare the target to that midpoint: - If it equals the midpoint, you’re done. - If the target is smaller, every element to the right of the midpoint is larger than the target (because the list is sorted), so you set the upper bound to mid − 1 and ignore the right half. - If the target is larger, you set the lower bound to mid + 1 and ignore the left half. That “ignore half” step is what halves the search interval each iteration. So the number of iterations grows very slowly: about log2(n) comparisons in the worst case (e.g., 16 elements → 4 checks). Requirements: data must be sorted and you must maintain correct lower/upper bounds (avoid off-by-one errors). For AP review, see the binary search study guide (https://library.fiveable.me/ap-computer-science-principles/unit-3/binary-search/study-guide/YADShVFQZbqwGicqH3ub) and try practice problems (https://library.fiveable.me/practice/ap-computer-science-principles).
What's the syntax for implementing binary search with `while` loops?
Binary search with a while loop follows the pattern: keep a lower and upper bound, compute mid, compare, and shrink the interval until you find the value or the interval is empty. Remember: data must be sorted (EK AAP-2.P.2) and watch off-by-one errors. Pseudocode (typical while-loop form): lower ← 0 upper ← n - 1 found ← false WHILE lower ≤ upper AND NOT found mid ← floor((lower + upper) / 2) IF list[mid] = target found ← true ELSE IF list[mid] < target lower ← mid + 1 ELSE upper ← mid - 1 END WHILE If found then return mid else return “not found”. Notes: this halving gives O(log n) iterations (EK AAP-2.P.1). Off-by-one bugs often come from whether indices are 0..n-1 or 1..n; adapt lower/upper initialization accordingly. For more review see the Topic 3.11 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-3/binary-search/study-guide/YADShVFQZbqwGicqH3ub) and practice problems (https://library.fiveable.me/practice/ap-computer-science-principles).
When should I use binary search vs just searching through an array normally?
Use binary search when the data is sorted and you care about efficiency. Binary search starts at the middle, halves the search interval each iteration, and runs in logarithmic time ≈ log2(n) iterations (so for 500 items you’ll examine ~9–10 elements)—that’s why the CED says it’s often more efficient than sequential/linear search (EK AAP-2.P.1, AAP-2.P.3). Use a linear (sequential) search when the array is unsorted, when n is tiny (e.g., < ~20) and simplicity matters, or when you’ll only do one lookup and don’t want the cost of sorting first. Remember: data must be sorted to use binary search (EK AAP-2.P.2). On the AP exam, they test you on iteration counts and the sorted-data requirement (LO AAP-2.P), so be ready to justify why binary is faster for large sorted lists and to compute approx iterations. For a focused review check the Topic 3.11 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-3/binary-search/study-guide/YADShVFQZbqwGicqH3ub) and practice problems (https://library.fiveable.me/practice/ap-computer-science-principles).
Why does the array have to be sorted for binary search to work?
Binary search works by comparing the target to the middle element and then “eliminating” half the list each step (EK AAP-2.P.1). That elimination only makes sense if you know which half contains larger or smaller values—i.e., the data must be in sorted order (EK AAP-2.P.2). If the array isn’t sorted, comparing to the middle gives no reliable information about where the target could be, so you can’t safely discard the left or right half. With a sorted list, each comparison shrinks the search interval by about half, so the max number of iterations is about log2(n) (LO AAP-2.P.a), which is why binary search is more efficient than linear search on sorted data. For a quick refresher, check the Topic 3.11 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-3/binary-search/study-guide/YADShVFQZbqwGicqH3ub)—and practice problems are at (https://library.fiveable.me/practice/ap-computer-science-principles).
How many iterations does binary search take to find a value in an array of 100 elements?
Binary search on 100 sorted elements takes at most ceil(log2(100)) = 7 iterations in the worst case. Each iteration halves the search interval (check the middle, then keep either the left or right half), so after 7 halvings you’ve reduced 100 down to 1 or fewer elements. It can take fewer iterations if the value is found earlier. Remember: binary search requires the data to be sorted (EK AAP-2.P.2) and each step eliminates half the remaining elements (EK AAP-2.P.1). This is why binary search runs in logarithmic time and is much faster than linear search on sorted data (EK AAP-2.P.3). For more practice and AP-style questions on this topic, check the Topic 3.11 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-3/binary-search/study-guide/YADShVFQZbqwGicqH3ub) and the full Unit 3 overview (https://library.fiveable.me/ap-computer-science-principles/unit-3). You can also drill thousands of practice problems at (https://library.fiveable.me/practice/ap-computer-science-principles).
Can someone help me trace through this binary search code step by step?
Pick a concrete example and trace it—that makes binary search obvious. Suppose sorted list = [2, 5, 7, 11, 14, 18, 21] (n = 7) and target = 14. Start with lower = 1, upper = 7 (or 0 and 6 if 0-based). 1) Iteration 1: mid = floor((lower+upper)/2) = floor((1+7)/2) = 4 → element = 11. Compare: 11 < 14 → eliminate left half including mid. Set lower = mid + 1 = 5. (You’ve eliminated 4 elements; search interval halved.) 2) Iteration 2: mid = floor((5+7)/2) = 6 → element = 18. Compare: 18 > 14 → eliminate right half including mid. Set upper = mid - 1 = 5. 3) Iteration 3: mid = floor((5+5)/2) = 5 → element = 14. Compare: equal → found at index 5. Stop. Notes tied to the CED: data must be sorted (EK AAP-2.P.2). Each iteration eliminates half the interval (EK AAP-2.P.1) so worst-case iterations ≈ ceil(log2 n) (LO AAP-2.P.a). Watch off-by-one errors when updating bounds. For more examples and AP-aligned practice, see the Topic 3.11 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-3/binary-search/study-guide/YADShVFQZbqwGicqH3ub) and lots of problems at (https://library.fiveable.me/practice/ap-computer-science-principles).
I'm confused about how to calculate the middle index in binary search without getting array out of bounds errors
Use two pointers for an inclusive search interval: low and high (indices). Compute the middle as mid = low + (high - low) // 2 instead of (low + high) // 2—that formula avoids integer overflow and is safe in any language. Then compare target to A[mid]. If equal, you’re done. If target > A[mid], set low = mid + 1. If target < A[mid], set high = mid - 1. Repeat while low <= high. Key things that avoid out-of-bounds and off-by-one errors: - Keep a clear loop invariant: the target (if present) is always within [low, high]. - Use inclusive bounds and update with mid ± 1, not ± 0. - Stop when low > high (means element not found). Remember binary search requires sorted data (EK AAP-2.P.2) and runs in O(log n) iterations (EK AAP-2.P.1). For a quick refresher, check the Topic 3.11 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-3/binary-search/study-guide/YADShVFQZbqwGicqH3ub). For more practice, Fiveable has lots of unit review and practice problems (https://library.fiveable.me/ap-computer-science-principles/unit-3 and https://library.fiveable.me/practice/ap-computer-science-principles).
What happens if the value I'm searching for isn't in the sorted array using binary search?
If the value isn’t in the sorted array, binary search keeps halving the search interval (updating lower or upper bound based on comparisons) until the interval is empty—meaning there are no elements left to check. At that point the algorithm terminates and reports “not found” (or returns a sentinel like −1). This follows EK AAP-2.P.1: binary search repeats eliminating half the data until the value is found or all elements have been eliminated. A couple of practical notes for the AP exam: the maximum number of iterations is on the order of log2(n) (use the ceiling), so binary search is logarithmic time and much faster than linear search on large sorted lists. Be careful with off-by-one errors when updating bounds (lower = mid+1 or upper = mid−1) so you actually detect the empty interval. For a quick review, check the AP Topic 3.11 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-3/binary-search/study-guide/YADShVFQZbqwGicqH3ub) and practice questions (https://library.fiveable.me/practice/ap-computer-science-principles).
Why is binary search more efficient than linear search and when should I use each one?
Binary search is more efficient because each comparison cuts the search interval in half, so the number of iterations grows logarithmically (about log2(n)). For example, a sorted list of 500 items needs at most about 9 comparisons (log2(500) ≈ 8.97)—that’s why EK AAP-2.P.1 and AAP-2.P.a emphasize halving and iteration count. But binary search requires sorted data (EK AAP-2.P.2); if the list isn’t sorted you can’t use it. Use linear (sequential) search when: - The data is unsorted or expensive to sort. - The list is very small or you’ll only do one search. - You need the first match in a stream or you expect early hits. Use binary search when: - The data is sorted and you’ll do many searches (faster overall). - You need logarithmic time performance for large n. For AP exam prep, remember the two CED points: data must be sorted and you should be able to compute iteration counts (logarithmic). Review Topic 3.11 on Fiveable (study guide: https://library.fiveable.me/ap-computer-science-principles/unit-3/binary-search/study-guide/YADShVFQZbqwGicqH3ub) and practice problems (https://library.fiveable.me/practice/ap-computer-science-principles).
How do I know how many times binary search will loop before finding or eliminating a target value?
Count how many times you halve the search interval. For a sorted list of n elements, the worst-case number of comparisons (or loop iterations) is floor(log2 n) + 1—so binary search runs in Θ(log n) time. Examples: n=1 → 1 iteration; n=2 → 2; n=3 → 2; n=4 → 3. That “+1” comes from the initial middle check, and the floor(log2 n) counts how many times you can halve before you’re down to one element. Remember: this only applies if the data are sorted (EK AAP-2.P.2), and binary search eliminates half the data each iteration (EK AAP-2.P.1). For AP practice and to see this tied to the CED question, check the binary search study guide (https://library.fiveable.me/ap-computer-science-principles/unit-3/binary-search/study-guide/YADShVFQZbqwGicqH3ub) and try more problems on Fiveable’s practice page (https://library.fiveable.me/practice/ap-computer-science-principles).
What are the requirements for binary search to work properly on a data set?
Binary search only works if the data meets a few clear requirements: - The data set is sorted (EK AAP-2.P.2). If it isn’t sorted, binary search can’t guarantee eliminating half the data. - You can access elements by index (or otherwise jump to the middle of the current interval) so you can check the midpoint value and compare (midpoint, lower bound, upper bound, comparison operation). - You maintain and update a search interval (lower and upper bounds) and recalculate the midpoint each iteration, halving the interval until you find the value or the interval is empty (EK AAP-2.P.1). - Be careful with off-by-one errors when updating bounds (loop invariant helps reason correctness). Performance note: max iterations ≈ ceil(log2(n)) for n elements (logarithmic time). For AP review, see the Topic 3.11 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-3/binary-search/study-guide/YADShVFQZbqwGicqH3ub) and practice problems (https://library.fiveable.me/practice/ap-computer-science-principles).