Welcome to Searching Algorithms!
Searching is one of the most fundamental things we do in Computer Science. Whether you are looking for a contact on your phone, a specific video on YouTube, or a high score in a database, an algorithm is working behind the scenes to find that data. In this chapter, we will look at the two main ways computers find what they are looking for: Linear Search and Binary Search.
Don’t worry if algorithms sound intimidating at first! By the end of these notes, you’ll see they are just like methods we use in real life every day.
1. Linear Search: The "One-by-One" Method
The Linear Search is the simplest way to find something. It starts at the very beginning of a list and checks every single item, one after the other, until it finds the target or reaches the end.
How it works (Step-by-Step):
1. Start at the first item in the list.
2. Compare this item to the one you are looking for (the target).
3. If it matches, stop! You’ve found it.
4. If it doesn't match, move to the next item.
5. Repeat steps 2-4 until you find the item or have checked the whole list.
Real-World Analogy:
Imagine you are looking for a specific shirt in a messy laundry basket. You pick up the first shirt, check it, put it aside, pick up the second, check it, and so on. That is exactly how a Linear Search works!
Efficiency Tip:
The syllabus mentions two versions of this search:
- Inefficient version: The algorithm checks every item even if it has already found the target.
- Advanced version: The algorithm stops immediately as soon as the item is found. This saves time!
Quick Review: Linear search works on any list, whether it is sorted (in order) or unsorted (random).
Key Takeaway: Linear search is simple but can be slow if you have a huge list, because in the worst-case scenario, you have to check every single item.
2. Binary Search: The "Divide and Conquer" Method
The Binary Search is much faster than Linear Search, but it has one very important rule: The list MUST be sorted (e.g., in alphabetical order or from smallest to largest number).
How it works (Step-by-Step):
1. Find the middle item of the list.
2. Compare the middle item to your target.
3. If the middle item is the target, you're done!
4. If your target is smaller than the middle item, throw away the right half of the list.
5. If your target is larger than the middle item, throw away the left half of the list.
6. Repeat the process with the remaining half until the item is found.
The Math Behind the Middle:
To find the middle index, we often use this simple formula:
\( \text{mid} = \text{integer}(\frac{\text{first\_index} + \text{last\_index}}{2}) \)
Real-World Analogy:
Think of looking for a word in a printed dictionary. You don't start at page 1 and read every word (Linear Search). Instead, you open it in the middle. If the word you want comes "before" the middle page, you ignore the whole second half of the book and search only the first half.
Did you know? Binary search is so fast that even if you had a list of 1 million items, it would take a maximum of only 20 steps to find your target!
Key Takeaway: Binary search is incredibly fast for large amounts of data, but it only works if the data is already ordered.
3. Comparing the Two Algorithms
In your exam, you might be asked to compare these two. Here is a simple breakdown to help you remember the differences:
Linear Search
- Requirement: None. Works on sorted or unsorted lists.
- Time Efficiency: Slow for large lists. The time taken grows linearly with the number of items.
- Best used when: The list is small or the data is completely unsorted.
Binary Search
- Requirement: Data must be sorted first.
- Time Efficiency: Very fast. Even if the list doubles in size, it only takes one extra step to search it.
- Best used when: You have a large, sorted list of data.
Common Mistake to Avoid: Never try to use a Binary Search on an unsorted list in an exam question. You must state that the list needs to be sorted first!
Memory Aids and Tricks
- Linear = Line. Think of a Line of people. You check them one by one.
- Binary = Bi (two). Think of a Bicycle with two wheels. You are always splitting the list into two parts.
Summary Checklist
- Can you trace a Linear Search through a list of numbers?
- Do you know that an efficient Linear Search stops once the item is found?
- Can you explain why a list must be sorted for a Binary Search?
- Can you calculate the middle point of a list for a Binary Search step?
- Can you explain which algorithm is faster for a list of 10,000 sorted names? (Hint: It’s Binary!)
Keep practicing by drawing out small lists of numbers and "acting out" the algorithms with your pen. You'll be an expert in no time!