Linear Search Vs Binary Search

All programmers are familiar with Linear search and Binary Search. Generally we use use them to search any element and its location. Today’s discussion is about the comparison of these two searching algorithm.

1. Sequential:

Linear search follows sequence and Binary search doesn’t follow. Linear search starts searching from the starting to ending point. Binary searching starts from middle point.

2. Sorted:

For binary search we need sorted elements . Linear search does not need sorted elements .

It searches all the element in all position till it gets the desired elements.

3. Comparison:

The number of comparison in Binary Search is less than Linear Search as Binary Search starts from the middle for that the total comparison becomes half of Linear Search.

3. Comparison:

The number of comparison in Binary Search is less than Linear Search. Total number of comparison Binary Search is half of Linear Search.

4. Time Complexity:

From the following image we can understand the time complexity of an Algorithm.

The time complexity of Linear search is:

a . Best case = O(1)

b . Average case = n(n+1)/2n = O(n)

c . Worst case = O(n)

The time complexity of Binear search is:

a . Best case = O(1)

b . Average case = logn(logn+1)/2logn = O(logn)

c . Worst case = O(logn)

So we can assume that the time complexity of Binary search is less than Linear search.

5. Space Complexity:

Space complexity of Linear Search is O(1) and Binary Search is O(logn). In this case Binary Search is better than Linear Search.

So we can assume that when we need better complexity then we should use Binary Search algorithm. We can’t apply Binary Search in searching elements in a unsorted list. Happy Coding!