Searching Algorithms: Summary
Explore the fundamentals of searching algorithms with a focus on linear and binary search techniques. Learn how linear search operates on any dataset and why binary search excels with sorted data. Understand key differences, performance impacts as input size grows, and practical decision-making for selecting the appropriate search method.
Having studied both search algorithms, the table below summarizes their key differences.
Feature | Linear Search | Binary Search |
Data requirement | Works on ordered or unordered collections (e.g., arrays, lists) | Requires sorted data in an indexed structure (e.g., arrays, lists) |
Time complexity | O(n) in the worst case | O(log n) in the worst case |
Space complexity | O(1) |
|
How it works | Checks elements one by one from start to end | Repeatedly divides the search space in half |
Best for | Small collections, unsorted data, single lookups | Large sorted collections, repeated lookups |
Implementation | Simpler often has a single loop | Slightly more complex, uses variables such as low, high, and mid |