Binary search is not well understood

Empieza revisando el BinarySearch README, el comportamiento del constructor y el test que requiere ArgumentError para entradas sin ordenar. Lee la discusión antes de elegir el alcance, ya que el issue propone cambios en el README, comprobaciones del constructor, comprobaciones de rikki y la eliminación de tests. Se considera terminado cuando la guía educativa acordada y los tests correspondientes se hayan actualizado de forma coherente.

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.