Linear search Vs. Binary search | Data structure
A linear search algorithm search one item at a time, without jumping to any item.
- The worst case complexity is O(n).
- Time taken to search elements keep increasing as the number of elements are increased.
A binary search however, cut down your search to half as soon as you find middle of a sorted list.
- The middle element is used to check if it is greater than or less than the value to be searched.
- Accordingly, search is done to either half of the given array list.
|
Linear Search |
Binary Search |
|
Binary search requires the input data to be sorted
|
linear search doesn't |
|
Binary search requires an ordering comparison
|
linear search only requires equality comparisons |
|
Binary search has complexity O(log n) |
linear search has complexity O(n) |
|
Binary search requires random access to the data |
linear search only requires sequential access |