# Why is binary search,which needs sorted data, considered better than linear search?

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?

• As with so many other things, it all comes down to: "It depends... ;)" 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. 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. Jul 19 '13 at 19:58

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.

• If you are only doing something once, not much point in optimizing it.
– user251748
Sep 25 '17 at 13:53

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.

• If you search often and insert often, you might look at more complicated data structures (e.g. binary trees). 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. 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)`

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?

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.

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.

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.

While a lot of good reasons for "binary search is better" have already been listed, we might also have a look at the advantages from a user perspective:

While you can normally live very well with the small waiting time split between data entering actions when you do a sorted insert, you want "search" to be as fast as possible. From a user's point of view, sorted insert combined with a binary search gives the best possible user experience.