Hacker News Reader

Comment by IncreasePosts | Hacker News Reader

> This one also makes that assumption, but in some cases if that assumption is violated it returns an error rather than silently returning a meaningless

Sometimes returning an error and sometimes returning an incorrect value doesn't sound like a binary search that is "absolutely reliable".

Also, s/consolation/consultation/

View on HN

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.

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.

Binary search only works if you suppose the data is well structured. If you perform the search and in the meantime you spot a passing inconsistency, you can interrupt everything and throw an error. But other than that, checking the entire structure negates the entire point of the algorithm

It doesn't seem possible to determine if the predicate is monotonic without doing a full scan, thus not being a binary search.

Reply on news.ycombinator.com