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?
Best Answer
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.