Binary search is not well understood

まず BinarySearch README、コンストラクターの動作、およびソートされていない入力に対して ArgumentError を要求するテストを確認します。issue では README の変更、コンストラクターのチェック、rikki のチェック、テストの削除が提案されているため、範囲を決める前に議論を読んでください。合意した教育的ガイダンスと対応するテストが一貫して更新されていれば完了です。

The whole point of binary search is to do array searches in logarithmic time, instead of in linear time. Having recently taken a look at the implementations, I have not found a single one that actually does this. In fact, all the solutions I've looked at actually check to see that the array given is sorted by sorting copy of the array. This means that the solution is at least O(n) because it needs to create a copy and depending on the sorting algorithm (I think the default is merge sort), might well be O(n log n).

I think the README should make this point a lot clearer, but exercism might not be the best place to teach algorithmic complexity (or it might, I don't know). Perhaps we could add a rikki nit to check if the BinarySearch constructor sorts the input array and a call is made to the constructor in the code. Another rikki point might be to scan the code for array slices as these also create copy arrays, violating the O(log n) goal.

While it is possible to actually implement the problem as it stands in an O(log n) manner, by not using recursion, it is rather limiting. Not to mention the fact that non-recursive binary search is actually a very tricky algorithm to code up (it's easy to get off-by-one errors). It is also possible with recursion, but people tend to have difficulty in coming up with the idea of passing the start and end indices around as parameters. That would be a nice thing to teach, but is not really in the spirit of Ruby (programmer happiness)

We should also remove the test that asks clients to raise an ArgumentError if the array given is not in sorted order. It seems to mislead a lot of people and doesn't even give us any security. There is nothing stopping clients from mutating the array passed in, but exercists don't seem to be aware of that. It's a false sense of security and so is arguably teaching them a bad habit.