Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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
3  
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
1  
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

6 Answers 6

up vote 29 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
2  
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

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

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

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

Your Answer

 
discard

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.