Key Terms
- Binary search: Searches a sorted list by repeatedly checking the middle item and discarding half of the list
- Sorted list: Items are in order, which binary search needs
- Midpoint: The middle position, found with (low + high) DIV 2
- Low and high pointers: Mark the start and end of the part still being searched
- Divide and conquer: Splitting a problem into smaller parts and dealing with each part
- Linear search: Checks each item in turn and works on unsorted lists
Must-Know Facts
- The list must be sorted before binary search is used
- Each step discards about half of the remaining items
- There are three outcomes at each step: found, search the left half, or search the right half
- The target is not found when the low pointer becomes greater than the high pointer
- About 10 comparisons are enough for a sorted list of 1000 items
- Binary search is best for large sorted lists that are searched often
Key Concepts
- Find the middle, compare, discard half, repeat
- Target larger than the middle item: keep the right half (low = mid + 1)
- Target smaller than the middle item: keep the left half (high = mid - 1)
- Main disadvantage: the data has to be sorted first, which takes time
- Linear search is simpler and is the better choice for short or unsorted lists
Common Mistakes
- Using binary search on an unsorted list: The halving only works because the items are in order, so an unsorted list gives wrong answers
- Keeping the wrong half: A larger target is always in the right half of a sorted list
- Forgetting the +1 and -1: The middle item has already been checked, so the new pointer moves past it
- Saying the middle is always the exact centre: With an even number of items, DIV drops the remainder, so the midpoint is the lower of the two middle positions
- Thinking binary search always beats linear search: On a short list, or one that is not sorted, linear search is the better choice
This topic summary covers Knowledge Organiser: Binary Search within Binary Search for GCSE Computer Science. Revise Binary Search in 3.1 Fundamentals of Algorithms for GCSE Computer Science with 15 exam-style questions and 10 flashcards. This is a high-frequency topic, so it is worth revising until the explanation feels precise and repeatable. It is section 8 of 8 in this topic. Use this topic summary to connect the idea to the wider topic before moving on to questions and flashcards.
Practice questions for Binary Search
Which of the following is a requirement before binary search can be used?
Describe how a binary search algorithm finds a target value in a sorted list.
Quick recall flashcards
What is the time complexity of binary search?
O(log n) - logarithmic time
What technique does binary search use?
Divide and conquer - repeatedly halves the search space