current community

your communities

more stack exchange communities

Stack Exchange
tour help
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.
up vote 1 down vote favorite

Binary Search, as we all know requires the elements to be sorted. But we have to take care of unsorted elements too, in the worst case. If the input size is very large, is it a good idea to sort the elements everytime? Can we not just check the elements that they are not sorted or not and proceed to sorting and proceed to sorting only if they are unsorted?

share|improve this question
    
It makes some sense to keep a known-sorted range and an unsorted range, with all new items in the unsorted range. That way, you can get O(n log m) rather than O(n log n) - where m is the size of the unsorted part - for sorting before searching. Sort the unsorted part, then do a merge to combine the two sorted ranges. Other than that - as ratchet freak says, confirming that a collection is sorted is as slow as doing a linear search into an unsorted collection anyway - you end up replacing an O(n) search with an O(n + log n) check-then-search, even assuming that the collection is always sorted. –  Steve314 May 24 '13 at 13:17

3 Answers 3

up vote 6 down vote

checking if a list is sorted defeats the purpose of the binary search (using less comparisons for a O(log n) running time instead of a O(n))

you are better of doing a linear search if you can't be sure the list is already sorted

share|improve this answer
up vote 1 down vote

I had to deal with something similar a long time ago.

Maintain a large sorted file and a small unsorted file. The small one contains items that haven't been merged in yet. Search the small one first, and, if that fails, then search the large one. "Every so often", like when the small file gets to be a certain fraction of the size of the large file, sort the small file and then merge it with the large one.

share|improve this answer
up vote 0 down vote

I was facing this problem just yesterday. Here are three bits of info I can offer that may help:

  1. Try to keep a database view of the data you need to query that is always sorted. For example, I had a huge (500k records), unsorted data table that contained, among other things, a column for CompanyName. In my application, I needed to search these records based on a given company name, which is ripe for a binary search. I simply created a sorted SQL view that contains only the CompanyName and the id (which is the primary key in the original table`. Now I query that directly from the application and get the result in under 10ms.
  2. If you can't ensure ahead of time that your data set is sorted, then make good use of hashtables and look into the "Quick Sort" algorithm. This is a O(log n) algorithm so if you run it first and then a binary search against your data it is surely faster than a linear search.
  3. Also, try to make good use of caching--if you have already sorted a given dataset, there is no reason to do it again for the next query against it.

Good luck!

share|improve this answer
1  
Quick sort is between O(n log n) and O(n^2). –  whatsisname May 24 '13 at 16:00
    
Fair point, but not the case if the sort is paralleled. I happen to use C# which has an extension method (.AsParallel()) that makes this process trivial. Either way, the points I made above are still valid even if my O(log n) assessment is arguably incorrect. –  Matthew Patrick Cashatt May 24 '13 at 16:36

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.