Welcome to Searching Algorithms!
Hi there! In this chapter, we are going to explore how computers find specific pieces of information within a large set of data. Whether you are looking for a contact in your phone or a website on Google, a searching algorithm is working behind the scenes. We will look at three main methods required for your AQA A Level: Linear Search, Binary Search, and Binary Tree Search. Don't worry if these sound complex; we will break them down step-by-step!
1. Linear Search: The "One-by-One" Method
The Linear Search is the simplest way to find something. Imagine you have a messy pile of socks and you are looking for the one with polka dots. You pick up the first one, check it, put it down, pick up the second one, and so on, until you find the right one.
How it works (Step-by-Step):
1. Start at the very beginning of the list (index 0).
2. Compare the current item with the target item you are looking for.
3. If they match, congratulations! You’ve found it.
4. If they don’t match, move to the next item in the list.
5. Repeat this until you either find the item or reach the end of the list.
Complexity and Efficiency
In Computer Science, we use Big O notation to describe how fast an algorithm is. For a Linear Search, the time complexity is \(O(n)\).
Why? Because in the worst-case scenario (where the item is at the very end or not there at all), you have to look at every single item (\(n\) items) in the list.
Quick Tip: Linear search is the only algorithm here that works on unsorted data. If your list is a total mess, Linear Search is your only choice!
Key Takeaway:
Linear Search is simple to code but slow for large amounts of data. Its time complexity is \(O(n)\).
2. Binary Search: The "Divide and Conquer" Method
The Binary Search is much faster, but it has one very important rule: The data MUST be sorted (e.g., in alphabetical or numerical order). If the list isn't sorted, Binary Search will not work!
Analogy: Think of looking for a word in a physical dictionary. You don't start at page 1. You open it in the middle, see if your word comes before or after that page, and throw away the half you don't need.
How it works (Step-by-Step):
1. Find the middle element of the list.
2. Compare the middle element to your target.
3. If the target is equal to the middle, you're done!
4. If the target is smaller than the middle, throw away the right half of the list.
5. If the target is larger than the middle, throw away the left half of the list.
6. Repeat the process with the remaining half until the item is found.
Complexity and Efficiency
Because you are halving the search area every single time, this algorithm is incredibly fast. The time complexity is \(O(\log n)\).
Common Mistake: Forgetting that the list must be sorted. On an exam, if a question asks you to perform a Binary Search on an unsorted list, your first step must be to mention that the list needs sorting first!
Key Takeaway:
Binary Search is very efficient for large datasets but requires sorted data. Its time complexity is \(O(\log n)\).
3. Binary Tree Search
A Binary Tree Search involves searching through a Binary Search Tree (BST). In this structure, each "node" has a value, and it can have up to two "children" (left and right).
The Golden Rule of BSTs:
For any node in the tree:
- Values smaller than the node go to the Left.
- Values larger than the node go to the Right.
Memory Aid: Left is Less!
How to Search a Binary Tree (Step-by-Step):
1. Start at the Root (the top node).
2. Is the Root the value you want? If yes, stop!
3. Is your target smaller than the current node? If yes, move to the Left child.
4. Is your target larger than the current node? If yes, move to the Right child.
5. Repeat until you find the value or hit a "null" (an empty spot), which means the value isn't in the tree.
Complexity and Efficiency
Just like Binary Search, if the tree is well-balanced, you are essentially halving the number of nodes to check at each step. Therefore, the time complexity is \(O(\log n)\).
Did you know? If a Binary Tree is very "unbalanced" (for example, every node only has a right child), it basically becomes a list, and the search speed drops back down to \(O(n)\)!
Key Takeaway:
Binary Tree Search uses a branching structure to find data. It is usually \(O(\log n)\), provided the tree is balanced.
Quick Review Table
Algorithm: Linear Search
Requires Sorted Data? No
Time Complexity: \(O(n)\)
Algorithm: Binary Search
Requires Sorted Data? Yes
Time Complexity: \(O(\log n)\)
Algorithm: Binary Tree Search
Requires Sorted Data? N/A (Data is structured in a tree)
Time Complexity: \(O(\log n)\)
Summary: Which one should I use?
1. If the data is small or unsorted, use Linear Search.
2. If the data is large and already sorted in an array, use Binary Search.
3. If you need to frequently add and remove items while keeping them searchable, a Binary Tree is often the best choice.
Don't worry if this seems tricky at first! The best way to learn is to try drawing out a list of numbers and "walking" through the steps of a Binary Search with your finger. You'll see how quickly the search area shrinks!