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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
checking if a list is sorted defeats the purpose of the binary search (using less comparisons for a
you are better of doing a linear search if you can't be sure the list is already sorted
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.
I was facing this problem just yesterday. Here are three bits of info I can offer that may help: