Binary search: check for non-sorted input defeats the purpose of binary search

[ryanplusplus]

Checking for non-sorted input is an O(n) operation. Performing the actual binary search is O(log(n)). Forcing the inclusion of an O(n) operation in the implementation of an O(log(n)) algorithm is confusing.

If you don't know that your input is sorted, there's no point in doing a binary search (sorting or checking for sorted input takes at least as long as a linear search), so I think this requirement should be removed.

[yurrriq]

You mean in the example implementation?

[ryanplusplus]

The example implementation has this issue, but only because the tests require it to check for sorted input. The example is particularly inefficient because it is recursive and checks for sorted input on each invocation, but this is a moot point if the tests are updated.

[yurrriq]

Aha. I'd suggest you raise an issue on x-common as this pertains to more than just the Clojure track and it'd be good to solve it universally.

[ryanplusplus]

There isn't a canonical test list for this exercise in x-common so for now this fix is only appropriate here. I'll put together a PR as long as you're in agreement that it should be fixed.

[yurrriq]

Definitely, but we should bring it up on x-common too.

[ryanplusplus]

Created an issue in x-common: exercism/problem-specifications#234