CODEWITHSUNDEEP
c++algorithmbinary-searchlinear-search
rishabh dixit
rishabh dixit

Reputation: 69

How is binary search faster than linear search?

We need a sorted array to perform a binary search. In that case, the time complexity is already greater than the linear search, so isn't linear search a better option in that case?

Upvotes: 0

Views: 7400

Answers (4)

Christopher Miller
Christopher Miller

Reputation: 3461

A linear search runs in O(N) time, because it scans through the array from start to end.

On the other hand, a binary search first sorts the array in O(NlogN) time (if it is not already sorted), then performs lookups in O(logN) time.

For a small number of lookups, using a linear search would be faster than using binary search. However, whenever the number of lookups is greater than logN, binary search will theoretically have the upper hand in performance.

So, the answer to your question is: Linear search and binary search perform lookups in different ways. Linear search scans through the whole array, while binary search sorts the array first. These two search techniques have differing time complexities, but that does not mean that one will always be better than the other.

Specifically, linear search works well when the size of the list is small and/or you only need to perform a small number of lookups. Binary search should perform better in all other situations.

Upvotes: 3

Yunfei Chen
Yunfei Chen

Reputation: 626

First of all for Binary Search the precondition is that the array is sorted, which means you do not need to resort it. Secondly if you are talking about integer arrays, you can use RadixSort O(d*n) or CountingSort O(n+l) which are similar to linear search in terms of complexity....

Upvotes: 1

Victor Gazzinelli
Victor Gazzinelli

Reputation: 91

Binary search is faster than linear when the given array is already sorted.

For a sorted array, binary search offers an average O(log n) meanwhile linear offers O(n).

For any given array that is not sorted, linear search becomes best since O(n) is better than sorting the array ( using quicksort for example O(n log n) ) and then applying binary search after that, thus given O(n log n + log n) complexity.

Upvotes: 0

asmmo
asmmo

Reputation: 7100

It'll be better if your container is sorted already or if you want to search for many values.

Upvotes: 1

Related Questions