About Binary Search

[albexl]

We had this Pull Request for implementing the Binary Search algorithm. We closed it because we are trying to find a way, using object-oriented programming, to represent Binary Search in a wider scenario, not just to find an element in a sorted array.

Any thoughts about how should we proceed?

[aniervs]

What about having a BinarySearch class, with each instance being initialised by receiving a function object. The class would have implemented the call magic method that would receive the left and right endpoints of the search + a few more arguments, such as:

• the length of the range on which to stop (this length could be a rational number, to support the search in floating-point numbers),
• the maximum number of iterations, which can also be used for floating-point search.
• whether to perform integer or real division by 2.

These arguments could have default values to make it easier for classical applications.

I would standardise the search this way:

• The function that directions the search should be Boolean and monotonic ($f(x) \implies f(y) \ \forall y > x$).
• $f(left)=false$ and $f(right)=true$
• make the search to return the first $x$ should that $f(x)=true$
  Other symmetric constructions are totally possible.
  Also, I would consider making some subclasses for specific types of search.

[aniervs]

I added a pull request with an initial version of this idea.
What do you think?

Also, as there are a bunch of assumptions in this implementation, I considered describing them in the definition of the class, along with some examples, similar to what official Python modules do.