Lesson Objective
- Understand the binary and linear search algorithms.
KS3, GCSE, A-Level Computing Resources
Imagine you have a giant phonebook with millions of names. Finding a specific number would take forever if you flipped through each page!
That's where search algorithms come in. They're like clever tools that help you find things quickly in big piles of data. Instead of checking everything one by one, they use shortcuts and smart tricks to zoom in on exactly what you need.
Think of it like searching for your friend in a crowded playground. You wouldn't look at every single person, right? You'd probably scan for their hair color, clothes, or maybe even hear their voice. Search algorithms do something similar, but for data like phone numbers or addresses. They make finding things fast and easy, even in massive amounts of information!
This search algorithm keeps dividing a sorted list in half until the desired result is found.
Here is a list of names:
Ali | Brad | Cora | Fred | Iman | Lyra | Nila | Omar | Pham | Ruth | Vlad |
---|
We are searching for the name Nila. The list has 11 items. Examine the middle one first.
Ali | Brad | Cora | Fred | Iman | Lyra | Nila | Omar | Pham | Ruth | Vlad |
---|
The middle item in the list is Lyra. Lyra comes before Nila alphabetically so we can discard all the names to the left of Lyra, including Lyra. Now we only have 5 names to search.
Ali | Brad | Cora | Fred | Iman | Lyra | Nila | Omar | Pham | Ruth | Vlad |
---|
Examine the middle name of the remaining list. The middle name is Pham. Nila comes before Pham so we can discard all the names from Pham to Vlad.
Ali | Brad | Cora | Fred | Iman | Lyra | Nila | Omar | Pham | Ruth | Vlad |
---|
Two names remain. The "middle" name is taken to be the first one (e.g. In a list of 4 names, the 2nd name would be the middle one). In the list of 2, examine thie 1sr item (Nila). Nila has now been found.
Imagine you have a messy pile of clothes and you need to find a specific shirt. You wouldn't be able to quickly narrow it down by diving straight to the middle, right? That's like binary search, which needs things to be neatly ordered.
Instead, you'd likely pick up each item one by one, checking if it's the shirt you're looking for. That's similar to a linear search, which goes through things sequentially until it finds what you need.
So, when things are mixed up, a linear search is like sifting through, while a binary search is like aiming straight for the target when things are lined up perfectly.
146 | 23 | 54 | 12 | 89 | 223 | 9843 | 2 | 389 |
---|
If the list to be searched is not sorted, it is not possible to do a binary search. A linear search may be carried out instead. Items are examined in the sequence. In the list above, to find the number 12, we would have to examine 146, 23, 54 and then 12.
Linear search does not need a sorted list. Binary search more efficient than linear - faster on larger lists. Binary search can not be done on unsorted lists. Linear search not good for large lists