Sign up ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

I have always heard that linear search is a naive approach and binary search is better than it in performance due to better asymptotic complexity. But I never understood why is it better than linear search when sorting is required before binary search?

Linear search is O(n) and binary search is O(log n). That seems to be the basis of saying that binary search is better. But binary search requires sorting which is O(n log n) for the best algorithms. So binary search shouldn't be actually faster as it requires sorting.

I am reading CLRS in which the author implies that in insertion sort instead of using the naive linear search approach it is better to use binary search for finding the place where item has to be inserted. In this case this seems to be justified as at each loop iteration there is a sorted list over which the binary search can be applied. But in the general case where there is no guarantee about the data set in which we need to search isn't using binary search actually worse than linear search due to sorting requirements?

Are there any practical considerations that I am overlooking which make binary search better than linear search? Or is binary search considered better than linear search without considering the computation time required for sorting?

share|improve this question
As with so many other things, it all comes down to: "It depends... ;)" –  Jeff Bridgman Jul 10 '13 at 13:16
If the list is already sorted, are you thinking that linear search is still better? That may be something to consider here. –  JB King Jul 10 '13 at 16:47
To anyone thinking of changing the title, please don't take out the part about sorted data because removing that makes this seem like a completely different question. –  Aseem Bansal Jul 19 '13 at 19:58

7 Answers 7

up vote 35 down vote accepted

Are there any practical considerations that I am overlooking which making binary search better than linear search?

Yes - you have to do the O(n log n) sorting only once, and then you can do the O(log n) binary search as often as you want, whereas linear search is O(n) every time.

Of course, this is only an advantage if you actually do multiple searches on the same data. But "write once, read often" scenarios are quite common.

share|improve this answer

The basic assumption is that you do not make one search.

So if you need to search the same data multiple times then you only have to sort once and can profit from binary search.

If you a searching often and have changing data it is worth to use a sorted list where new entries are sorted into the list.

So basically binary search is better when you search the same list multiple times without the need of resorting.

When you need to sort every time before searching there is no advantage.

Pleas note that there are sorting algorithms which are very fast when the list is already sorted (or nearly sorted). Most performance determinations expect an unsorted list.

share|improve this answer
If you search often and insert often, you might look at more complicated data structures (e.g. binary trees). –  MarkJ Jul 10 '13 at 16:46
@MarkJ the basic question of the original poster was about searching in a list. Else I agre with you completely. –  Uwe Plonus Jul 11 '13 at 7:47

because once you have a sorted list you don't need to re-sort it each time which means that if you have more than O(log n) searches sorting in advance will net you a gain win (O(n log n + k log n) vs O(k*n)

share|improve this answer

Imagine two phone books.

One phone book has the names in alphabetical order. To find the entry you want, you open in the middle, check the entry, then move forward or backward depending on whether you overshot or undershot.

The other phone book has the names in random order. To find the entry you want, you start at the beginning and continue until you find what you want.

Will the second book work in any reasonably sized city?

share|improve this answer

I think that the value of binary search over linear search is contextual. If you start with an enormous unordered data set and only plan to pluck a small number of items from it, then sorting and performing a binary search will be slow. If, however, you maintain an ordered list throughout the lifetime of your application and access it regularly, then binary search is a far better way to go.

share|improve this answer

In layman's words:

If you have an unordered list with ten billion items, and the item you happen to be looking for is the last one, you will end up reading the ten billion items.

In the case of the binary search, the indexing can be done just once. Later insertions can be made in the right place to maintain order.

share|improve this answer

Like many others have answered, binary search is indeed preferable because the sorting step can be done only once and the actual searching can then be done as many times as you like. However, for certain values of n (i.e. certain input sizes), binary search is always more performing than linear search (even for one single run).

The "tipping point" is computed by solving the asymptotical complexity equation:

n log n + log n = n

As you can see on Wolfram Alpha there is a numerical value for n that ensures that binary search and sorting is always faster than linear search alone. Of course the actual value of n that works in your case depends on many factors which may be difficult to estimate.

According to this interesting article by Mark Probst, which includes some nice in depth performance measurements on current processors:

If you need to search through a sorted array of integers and performance is really, really important, use linear search if your array is below around 64 elements in size, binary search if it’s above.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.