Linear search Vs. Binary search | Data structure

A linear search algorithm search one item at a time, without jumping to any item.

  1. The worst case complexity is O(n).
  2. 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.

  1. The middle element is used to check if it is greater than or less than the value to be searched.
  2. 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