Sorting and Searching Algorithms (AQA GCSE Computer Science): Revision Notes
Binary search
What are searching algorithms?
Searching algorithms are methods used by computers to find specific pieces of information in a collection of data, like finding a particular name in a phone book or a specific number in a list. These algorithms can also confirm whether something is definitely not present in the data.
The two main types of searching algorithms you need to know are linear search and binary search. While both can find the same results, they work in completely different ways and have very different levels of efficiency.
Linear search - the simple approach
Linear search is the most straightforward searching method. It works by checking each item in a list one by one, starting from the beginning, until it either finds what it's looking for or reaches the end of the list.
Here's how linear search works step by step:
- Start at the first item in the list
- Check if it matches what you're searching for
- If it matches, you've found it - stop searching
- If it doesn't match, move to the next item
- Repeat until you find the item or reach the end of the list
For example, if you wanted to find the number 9 in this list, linear search would check 7 first, then 2, then finally find 9 on the third attempt. If you were looking for the number 8, the algorithm would have to check every single item (7, 2, 9, 4, 3) before determining that 8 is not in the list.
Linear search is sometimes called "sequential search" because it searches through items in sequence, one after another.
The pseudocode for linear search looks like this:
REPEAT
Check one value (from the start)
IF value matches what is being searched for THEN
Output value
ELSE
Move to next value
ENDIF
UNTIL number is found OR end of list is reached
While linear search is simple to understand and implement, it can be very slow when dealing with large amounts of data. If you have a million items and the one you want is at the end, you'd need to check all million items!
Binary search - the efficient approach
Binary search is a much more efficient searching algorithm, but it comes with an important requirement: the list must be sorted in order first.
The list must be sorted in order first. This is absolutely crucial - binary search will not work correctly on an unsorted list.
How binary search works
Binary search uses a "divide and conquer" strategy. Instead of checking items one by one, it repeatedly cuts the search area in half by looking at the middle value of the current section.
Here's the process:
- Find the middle value of the sorted list
- Compare this middle value with what you're searching for
- If it's a match, you've found it - stop searching
- If the target value is smaller than the middle value, ignore the upper half of the list
- If the target value is larger than the middle value, ignore the lower half of the list
- Repeat this process on the remaining half until you find the item or determine it's not there
Worked example
Worked Example: Finding Letter Q Using Binary Search
Let's see binary search in action with a practical example. Imagine we have this sorted list of letters and we want to find the letter Q:
Original list: A, C, D, F, H, K, P, Q, S, T, V, W, Z
Step 1: Find the middle value The middle of our 13-item list is the 7th position, which contains the letter K. Since Q comes after K alphabetically, we can eliminate the lower half of the list (everything up to and including K).
Remaining list: P, Q, S, T, V, W, Z
Step 2: Find the new middle value With 7 items remaining, the middle position contains T. Since Q comes before T alphabetically, we can eliminate the upper half (T and everything after it).
Remaining list: P, Q, S
Step 3: Find the middle value again With 3 items left, we pick the middle one: Q. This matches what we're searching for, so we've found it!
The algorithm found Q in just 3 steps, even though it was the 8th item in a 13-item list.
Binary search pseudocode
REPEAT
Pick the middle value in a list (if even number of values, pick left-of-middle value)
IF value matches what is being searched for THEN
Output value
ELSE IF value searched for > middle value THEN
Discard middle value AND lower half of list
ELSE IF value searched for < middle value THEN
Discard middle value AND upper half of list
ENDIF
UNTIL (value found) or (list is of size 1 and value is not found)
Comparing linear and binary search
The difference in efficiency between these two algorithms becomes dramatic as the amount of data increases.
Efficiency comparison
Linear search:
- Works with any list (sorted or unsorted)
- In the worst case, checks every single item
- For 1 million items, might need up to 1 million comparisons
Binary search:
- Requires a sorted list
- Halves the search space with each comparison
- For 1 million items, needs a maximum of only 21 comparisons
This massive difference in efficiency is why binary search is so important in computer science. The ability to search through a million items in just 21 steps is what makes modern computing so fast!
Why is binary search so much faster?
Binary search halves the number of remaining items to check after each comparison. Starting with 1 million items:
- After 1 comparison: 500,000 items left
- After 2 comparisons: 250,000 items left
- After 3 comparisons: 125,000 items left
- And so on...
By the 21st comparison, you're guaranteed to have found the item or confirmed it's not there, regardless of where it was in the original million-item list.
When to use each algorithm
Use linear search when:
- Your data is not sorted and sorting it would take too long
- You're working with small amounts of data
- You need a simple algorithm that's easy to understand and implement
Use binary search when:
- Your data is already sorted or can be sorted efficiently
- You're working with large amounts of data
- You need maximum search speed and efficiency
Exam tips
Common Exam Points:
- Remember that binary search only works on sorted data - this is the most common mistake students make
- Practice tracing through binary search examples step by step
- Understand why binary search is more efficient: it eliminates half the remaining possibilities with each step
- Be able to write pseudocode for both algorithms
- Know that linear search is simpler but slower, while binary search is more complex but much faster
Remember!
Key Points to Remember:
- Binary search requires sorted data - it won't work properly on unsorted lists
- Binary search is much more efficient than linear search for large datasets, needing only 21 comparisons for a million items vs potentially a million comparisons for linear search
- Linear search works on any list but checks items one by one from start to finish
- Binary search works by repeatedly halving the search space by comparing with the middle value
- Both algorithms can confirm when an item is not present in the data, but binary search does this much faster