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?

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

You are watching: Is binary search faster than linear

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.

Share

Improve this answer

Follow

edited Sep 15 at 2:19

answered Jul 5 “20 at 18:04

TelescopeTelescope

1,71211 gold badge33 silver badges1818 bronze badges

Add a comment |

1

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

Share

Improve this answer

Follow

answered Jul 5 “20 at 18:04

asmmoasmmo

6,65911 gold badge77 silver badges2222 bronze badges

Add a comment |

1

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….

See more: Nearest Airports Near Ft Jackson South Carolina, Nearest Airport To Jackson, Sc, United States

Share

Improve this answer

Follow

answered Jul 6 “20 at 15:57

Yunfei ChenYunfei Chen

56266 silver badges1515 bronze badges

Add a comment |

0

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.

Share

Improve this answer

Follow

answered Jul 5 “20 at 18:11

Victor GazzinelliVictor Gazzinelli

8122 silver badges88 bronze badges

1

Add a comment |

## Your Answer

Thanks for contributing an answer to Stack Overflow!

Please be sure to *answer the question*. Provide details and share your research!

But *avoid* …

Asking for help, clarification, or responding to other answers.Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

See more: Which Of The Various Species Concepts Distinguishes, Chapter 22 Quiz Flashcards

Draft saved

Draft discarded

### Sign up or log in

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Submit

### Post as a guest

Name

Email Required, but never shown

### Post as a guest

Name

Email

Required, but never shown

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

## Not the answer you're looking for? Browse other questions tagged c++ algorithm binary-search linear-search or ask your own question.

The Overflow Blog

Featured on Meta

Related

3185

How do I iterate over the words of a string?

4470

How do I check if an array includes a value in JavaScript?

2408

What does O(log n) mean exactly?

2292

What are the basic rules and idioms for operator overloading?

2344

Why are elementwise additions much faster in separate loops than in a combined loop?

25895

Why is processing a sorted array faster than processing an unsorted array?

1671

Is

4034

How can I pair socks from a pile efficiently?

1986

What is the optimal algorithm for the game 2048?

Hot Network Questions more hot questions

Question feed

Subscribe to RSS

Question feed To subscribe to this RSS feed, copy and paste this URL into your RSS reader.

lang-cpp

Stack Overflow

Products

Company

Stack Exchange Network

site design / logo © 2021 Stack Exchange Inc; user contributions licensed under cc by-sa. rev2021.10.8.40416

Stack Overflow works best with JavaScript enabled

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.

## Discussion about this post