Hacker News Reader

It seems to me that it's impossible for a binary search to detect all errors. The precondition is that the list must be sorted, and to fully verify that assumption would be O(n). That would make your binary search no better than a linear search. So I can forgive the best-effort error checking.

View on HN

In theory at least that precondition could be guaranteed by a newtype like SortedList without requiring any linear scan, that would work at least for most cases where lists are sorted by an algorithm. Though not necessarily custom data which is constructed sorted/maintains it's sorting outside the algorithm, but you could perhaps have an unsafe constructor for your SortedList type. That should avoid a linear scan...

i am not sure i see a use case where that precondition is anything but mandatory (and at least a requirement in app space for the related data), if youre intending on making practical use of the algo.

if theres a risk that your input is unstable in ordering, then reaching for bsearch seems like a "premature optimization", and youd be better off with a straightforward linear scan until requirements (or your kanguage of choice's bst/heap/rbt equivalent), or data is preprocessed upstream in a way that makes sense for the contexts wanting to use it.

Reply on news.ycombinator.com