Mastering Optimization with Python/

...

/

Binary Search Implementation

Binary Search Implementation

Learn to implement the binary search algorithm and solve an example.

We'll cover the following...

We’ll implement the binary search algorithm and solve a practical problem with it. Let’s begin getting the idea behind the implementation, step by step.

Implementing binary search

The first decision to make is: Where do we begin the search? In this case, we don’t start from one place but two, simultaneously. We need two starting points. The only condition is that one should be in the invalid region and the other in the valid one. We’ll call them points aa and bb, respectively.

Once we have both initial points, we should approach the solution iteratively. The idea is to make both points closer each time while maintaining them in separate regions. When the points are close enough so we can say they’re the same, then that point is the solution.

Press + to interact
Binary search iterations
Binary search iterations

In these four iterations, we first move the right extreme point to the midpoint (to the left). In the last two iterations, we need to move the left extreme point to the midpoint (to the right).

But how do we modify the points and make sure they’re in different regions? The binary search algorithm follows a strategy that’s both simple and effective. Maybe the best way to explain it is by writing the code.

Press + to interact
def binary_search(a, b, constraint, tol=0.01):
  while abs(a - b) > tol:
    m = (a + b) / 2 # midpoint
    if constraint(m):
      b = m # b is stays in the valid region 
    else:
      a = m + tol
  return b

The method receives the initial interval, the constraint, and the optional error tolerance. In every iteration, point a is in the invalid region and b in the valid one.

Look how we divide the interval [a,b ...