Search Algorithms: Linear vs Binary Search

Searching for an item in a collection is a basic operation. The two most common approaches are linear search (scan until found) and binary search (halve the search space). This post compares them and when to use each.

Linear search

• Idea: Start at the beginning and check each element until you find the target or reach the end.
• Complexity: O(n) time, O(1) extra space.
• Requirements: Works on any sequence (ordered or not).
• Use when: Collection is unsorted, or small, or you only search once. In JavaScript: array.find(), array.indexOf() are linear.

Binary search

• Idea: Assume the collection is sorted. Compare the target to the middle element; if equal, done; if smaller, search the left half; if larger, search the right half. Repeat until found or the range is empty.
• Complexity: O(log n) time, O(1) extra space (iterative) or O(log n) stack (recursive).
• Requirements: Sorted data (or an ordering you can rely on).
• Use when: Data is sorted and you do many lookups, or n is large. Much faster than linear for large n.

Comparison

*If data isn’t already sorted, sorting just to do one binary search is O(n log n), which can be worse than one O(n) linear search.

When to use which

• Unsorted or one search: Use linear search (or your language’s indexOf / find).
• Sorted and/or many searches: Use binary search. If the collection isn’t sorted, consider sorting once (or keeping it in a structure that supports O(log n) lookups, e.g. a balanced tree) and then doing binary search (or tree lookups) for each query.

Summary

• Linear search: O(n), works on any order; use for unsorted or small data or single lookups.
• Binary search: O(log n), requires sorted data; use when data is sorted and you need fast, repeated lookups.
• Choose based on whether data is sorted and how often you search.