Binary search should not require a check for sorted input

[ryanplusplus]

See exercism/clojure#112

In short, the Clojure track requires a check for sorted input in the Binary Search exercise. This is confusing because the check for sorted input takes as long as a linear search such that the binary search operation takes longer than just doing a linear search. We should make sure this issue does not exist in other tracks.

[kotp]

xruby/binary-search does indeed check for sorted... raising an error if it is not.

[kytrinyx]

Agreed. If others are also in agreement, then we should write up an issue that can be cross-posted to all the tracks with blazon.

[Cohen-Carlisle]

I vote firmly in the binary search should not verify sorted input camp.
The fact that checking for sorted input defeats the purpose of binary sort is interesting and should probably be mentioned in the readme for curious students as well.

[kytrinyx]

The fact that checking for sorted input defeats the purpose of binary sort is interesting and should probably be mentioned in the readme for curious students as well.

Yeah, definitely.

[bglusman]

I came across this issue in Elixir exercise, which actually has another issue related to it's implementation details involving singly linked list, but when I saw the requirement to error if unsorted, I thought, OK, I can do that, I can just check if the middle pivot on recurse is ever on the wrong side of the value I recursed from... and I'd be OK with a failing test that wanted it to error in that case, as long as the input it passed was one that would require it to recurse and easily detect the unsorted list without traversing the entire list! So that's one option, but I admit it's a little awkward to do that, but maybe good practice.

[ryanplusplus]

@bglusman I don't think that's a real solution to the problem. It will catch some cases where ordering is not maintained, but it will not catch all of them.

[bglusman]

Well, it will catch all you can catch without necessarily violating the log N nature of binary search... what else makes sense really if you're going to test at all and not just falsely say not_found when it may be there but not sorted? Could change it to fall back on linear search when unsorted I guess

[petertseng]

A note against checking for sortedness had been added to #349. In addition, I'm going to recommend binary-search as a problem that is too specific in #761. This may result in changes to binary-search.

In the short term, if there are any tracks that ask for sortedness check, issues should be filed on the respective tracks.