Searching Algorithms: Linear and Binary Search
Why Search Algorithms Matter
Searching is one of the most common operations in computing. Every time you look up a contact on your phone, find a product on a retail site, or ask a search engine a question, a search algorithm is at work. The specification requires you to know two: linear search and binary search. Crucially, you must be able to compare them — choosing the right algorithm for a given situation is a practical engineering skill.
Linear Search
Linear search is the simplest approach. Starting at the beginning of the list, it checks each item in turn: does this match the target? If yes, return its position. If no, move to the next item. If the end of the list is reached without a match, the target is not present.
Linear search works on any list — sorted or unsorted. This makes it very flexible. You do not need to sort the data first, which saves time when you only need to search once.
Advantages of linear search: Simple to understand and implement. Works on unsorted data. Disadvantages: Slow for large datasets — in the worst case, every item must be checked. For a list of one million items, up to one million comparisons may be needed.
Binary Search
Binary search is far more efficient than linear search, but it has one important requirement: the data must already be sorted. Binary search works by repeatedly halving the search area.
The mechanics: Find the middle item of the current search area. If it equals the target, the search is done. If the target is smaller, discard the right half and repeat on the left. If the target is larger, discard the left half and repeat on the right. Continue until found or the search area is empty.
Sorted list: [3, 7, 11, 15, 19, 23, 27, 31, 35]
Step 1: Search area indices 0–8. Middle index = 4, value = 19. Is 23 = 19? No. Is 23 > 19? Yes. Discard left half. New search area: [23, 27, 31, 35] (indices 5–8).
Step 2: Search area indices 5–8. Middle index = 6, value = 27. Is 23 = 27? No. Is 23 < 27? Yes. Discard right half. New search area: [23] (index 5).
Step 3: Search area index 5. Middle = 23. Match found at index 5. Done in 3 comparisons.
Linear search on this list would have needed 6 comparisons to reach the same item. On a list of 9 items the saving is modest — the advantage becomes dramatic as the list grows.
Binary search halves the search area with every comparison. A sorted list of 1,000 items needs at most 10 comparisons with binary search, versus up to 1,000 with linear search. A list of one million items needs at most 20 comparisons. The data must be sorted first — binary search cannot work on unsorted data.
Comparing the Two Algorithms
The spec requires you to compare and contrast these algorithms in terms of time efficiency. Note that formal analysis (such as Big O notation) is not required — you only need to explain which is faster and why, in plain English.
Linear search:
- Works on sorted or unsorted data
- Simple to implement
- Slow for large lists — checks items one by one
- Best choice for small lists or lists that change frequently (re-sorting would cost more than a linear scan)
Binary search:
- Requires sorted data
- More complex to implement
- Very fast for large lists — halves the search area each step
- Best choice for large, stable (rarely changing) sorted datasets where fast repeated searches are needed
Choosing the Right Algorithm
If someone asks “which algorithm is better?”, the honest answer is: it depends. A phonebook app with 80 million entries benefits enormously from binary search — but the phonebook is kept in alphabetical order precisely to enable this. A small list of five items that changes every second is better served by linear search. Understanding this trade-off is what separates a competent programmer from someone who just follows a textbook.
Use linear search when: the list is small (the efficiency advantage of binary search is negligible), the data is unsorted and sorting it would cost more time than a single scan, or the list changes so frequently that maintaining a sorted order is impractical. Use binary search when: the dataset is large, the data is already sorted or is sorted once and searched many times, and fast repeated look-ups are a priority. In real systems, databases maintain sorted indexes precisely so that binary-style search can be used at speed.