|XP is just a number|
Re^3: Modified Binary Searchby BrowserUk (Pope)
|on Jan 14, 2010 at 11:03 UTC||Need Help??|
Depending on the data set this additional step could eat away any savings from performing a few steps more in the binary search.
Sorry, but that would only be true if a binary search worked on data with duplicates. It doesn't.
So you have to factor in the additional complexity of the basic search plus the steps required to locate the appropriate (upper or lower) boundary of the run of duplicates.
I don't believe it is possible to code a search over sorted data with duplicates that comes even close to be O(log N). Even in theory. And in practical implementations, it'd be far slower.
Feel free to prove me wrong :)
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.