Binary Search: Beyond Arrays

Binary search is one of the most common ways of searching through any sorted list.

It is based on how our brain solves this problem intuitively. Just consider the following psuedocode:

BinarySearch(Arr,value,low,high):
  if (high<low):
    	return notFound
    mid = (high + low)/2
    if (Arr[mid]<value)
    	return BinarySearch(Arr,value,mid+1,high)
  if (Arr[mid]>value)
    	return BinarySearch(Arr,value,low,mid-1)
  return mid

Now isn't it exactly like how we search for things like our enrollment number in the registration list for a particular class.

• We look at the first roll number and the last number.
• Then we narrow the search window down until we reach the spot our roll number would (most likely) be at.

This is a rather short crash course on the applications of Binary Search. However, did you know that this approach can also be applied to solving equations? Now that sounds and fun and that is exactly what we are going to explore next.

Beyond Arrays

Now this happened last year. I had a particluar problem in my hydrology paper, which required me to find an approximate solution to:

• x log(x) + x = 6000
• or, x log(x) + x - 6000 = 0.
  All I had was a calculator that could do logarithms. So here is my approach:

1. Check for x=1 and a number where function has a sign opposite to x=1(here say x=1000)
2. initialize low =1 and high=1000.Now result must lie in the interval (low,high)
3. Start a loop where for every turn:
   • mid = (high+low)/2
   • if(abs(xlog(x)+x-6000)<0.2) #for x == mid then break
   • else update high and low using mid so that sign of function at them is opposite.
     I was able to get within an error of 10 within 6 steps of calculations by my calculator.

Below is the python code for the approach.

from math import log
def myFunc(x):
    return 1000*log(x) + (x) - 6000

low = 1
high = 1000
mid = (high+low)/2
while(abs(myFunc(mid))>0.2):
    print mid,myFunc(mid)
    if myFunc(mid)*myFunc(high)>0:
        low,high = low,mid
    else:
        low,high = mid,high
    mid = (high+low)/2.0
print mid,myFunc(mid)

And its output:

500 714.608098422
250.5 -226.041079475
375.25 302.842470514
312.875 58.6787497519
281.6875 -77.5141995491
297.28125 -8.04008959327
305.078125 25.6460163482
301.1796875 8.88674257264
299.23046875 0.444543723073
298.255859375 -3.79243398916
298.743164062 -1.67261475274
298.986816406 -0.613703461946
299.108642578 -0.0844969238451

As you can clearly observe, we have reached an acceptable solution within 13 steps.

Inference

What we can infer from the process above is that binary search is an intuitive algorithm, whose usage should not be limited to array searching only. Using the above approach, you can solve a wide variety of simple equations — logarithmic, exponential, and polynomial alike.

On a different philosophical note, the real number line is nothing but a sorted array, and every equation solving problem is thus analogous to a search problem. Since binary search happens to be an excellent search algorithm, we can use it for all such problems. And this, my friends, was my take on the Binary Search Algorithm.

I am always available to answer any questions you may have at Abhay447!