Linear Search (AQA GCSE Computer Science): Revision Notes
Linear search
What is a searching algorithm?
When you need to find specific information in a list of data, you use a searching algorithm. Think of it like looking for a particular book in a library or finding a friend's name in your contacts list. A searching algorithm is a set of instructions that tells the computer exactly how to look through data to find what you're looking for.
Searching algorithms are fundamental to computer science and are used everywhere - from search engines finding web pages to databases locating specific records.
There are different ways to search through data, but the most straightforward method is called a linear search. This is the simplest type of searching algorithm and works just like how you might naturally search through a list by checking each item one by one.
How does linear search work?
Linear search is pretty much what it sounds like - it searches in a straight line through your data. Here's how it works:
- Start at the beginning of the list
- Check the first item - is it what you're looking for?
- If yes - great! You've found it and can stop searching
- If no - move to the next item in the list
- Repeat this process until you either find the item or reach the end of the list
- If you reach the end without finding the item, then it's not in the list
The key thing to remember is that linear search checks every single item in order from start to finish until it finds what it's looking for.
Linear search is sometimes called "sequential search" because it examines data sequentially, one item after another.
Linear search example
Let's see how this works with a practical example. Imagine you have a list of numbers and you want to find the number 9:
Worked Example: Finding Number 9
Here's what happens step by step:
- Step 1: Check the first number (7) - is it 9? No, so move to the next
- Step 2: Check the second number (2) - is it 9? No, so move to the next
- Step 3: Check the third number (9) - is it 9? Yes! Found it!
The search stops here because we've found our target value.
But what if we were looking for the number 8? The algorithm would:
- Check 7 (not 8), then 2 (not 8), then 9 (not 8), then 4 (not 8), then 3 (not 8)
- Reach the end of the list without finding 8
- Conclude that 8 is not in the list
Pseudocode for linear search
In computer science, we often write pseudocode to show how an algorithm works. Here's the pseudocode for linear search:
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
Pseudocode is a way of describing algorithms using simple, everyday language mixed with some programming-like structure. It helps us plan algorithms before writing actual code.
This pseudocode shows the repeating process of checking each value and either finding the target or moving to the next item.
Advantages and disadvantages of linear search
Advantages:
- Simple to understand - it works exactly like how humans naturally search
- Works on any list - doesn't matter if the data is sorted or unsorted
- Easy to programme - requires minimal code to implement
Disadvantages:
- Can be very slow - if you have a million items and the one you want is at the end, you have to check all million items
- Inefficient for large datasets - there are much faster searching methods available for organised data
Think of it this way: if you're looking through a small box of 20 photos, checking each one isn't a big deal. But if you're looking through thousands of photos, you'd want a more efficient method!
Critical Limitation: Linear search has a time complexity of O(n), meaning in the worst case, it might need to check every single item in the list. For large datasets, this becomes very inefficient compared to other search algorithms like binary search.
Exam tips
Essential Exam Points:
- Remember that linear search is also called sequential search because it checks items in sequence
- Linear search works on both sorted and unsorted lists
- The worst-case scenario is when the item you're looking for is at the very end of the list (or not in the list at all)
- Always mention that it checks items one by one from the beginning in your exam answers
Remember!
Key Points to Remember:
- Linear search checks each item in a list one by one from start to finish
- It's the simplest searching algorithm but can be slow for large datasets
- The search stops immediately when the target item is found
- If the algorithm reaches the end without finding the item, it confirms the item is not in the list
- Linear search works on any type of list, whether it's organised or not