Linear Search Vs Binary Search

1_xz1gwaJr-7URg8nRXs1Fng.png

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

1. Sequential:

The linear search follows sequence and Binary search doesn’t follow. The linear search starts searching from the starting to ending point. Binary searching starts from the 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 until 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 is log2N.

4. Time Complexity:

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

1_lpjpuuNJkj73zEOO_atpkA.png

The time complexity of Linear search is:

aBest case = O(1)

bAverage case = n(n+1)/2n = O(n)

cWorst case = O(n)

The time complexity of Linear search is:

aBest case = O(1)

bAverage 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:

The space complexity of Linear Search is O(1) and Binary Search is O(1).

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

You can find this article on: Hacker Noon

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s