Why This Matters
Binary search is one of the highest-leverage DSA patterns, but only when the problem has order. Linear search is slower asymptotically but works on unsorted data and arbitrary predicates.
Decision Rule
Use linear search when the input is small, unsorted, or the predicate has no monotonic structure. Use binary search when the candidate space is sorted or the yes/no predicate flips once.
Comparison Table
| Feature | Linear search | Binary search |
|---|---|---|
| Requirement | none beyond iterable data | sorted data or monotonic predicate |
| Time | O(n) | O(log n) |
| Access pattern | sequential | middle index jumps |
| Works on linked list | yes | not efficiently |
| Common use | small scans, unsorted data | sorted arrays, answer search, boundary finding |
Worked Example
To find 17 in [3, 9, 17, 22, 30], linear search checks 3, then 9, then 17.
Binary search checks the middle first. If the middle is too small, it discards the left half. Each comparison removes half the remaining candidates because the array is sorted.
Common Mistakes
| Mistake | Correction |
|---|---|
| Applying binary search to unsorted data. | Sorting or monotonicity is required. |
| Writing off-by-one boundaries casually. | Decide whether the interval is closed or half-open and stay consistent. |
| Forgetting that sorting costs time. | Sorting just to binary search once may be worse than one scan. |
Diagnostic Questions
| Question | Answer signal |
|---|---|
| Which search works on unsorted arrays? | Linear search. |
| What property makes binary search valid? | Ordered candidates or a monotonic predicate. |
Why is binary search O(log n)? | Each step halves the search interval. |
Exercises
- Beginner: Search for a value linearly in a short unsorted list.
- Beginner: Run binary search by hand on a sorted list.
- Beginner: Identify whether a predicate is monotonic.
- Intermediate: Implement lower bound with a half-open interval.
- Intermediate: Explain when sorting plus binary search is worth it.
- Challenge: Use binary search on answer for minimum feasible capacity.
References
- MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- MIT OpenCourseWare. 6.006 Binary search and sorting materials, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/