4 ms·

> 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 Someti

> 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/

edflsafoiewq 2y ago
It doesn't seem possible to determine if the predicate is monotonic without doing a full scan, thus not being a binary search.
fallingsquirrel 2y ago
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.
- ratmice 2y ago
  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...
- _proofs 2y ago
  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.
Almondsetat 2y ago
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
deleted 2y ago
[deleted]

edflsafoiewq 2y ago

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

fallingsquirrel 2y ago

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.

ratmice 2y ago
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...
_proofs 2y ago
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.

Almondsetat 2y ago

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

deleted 2y ago

[deleted]