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.
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:
- Check for x=1 and a number where function has a sign opposite to x=1(here say x=1000)
- initialize low =1 and high=1000.Now result must lie in the interval (low,high)
- 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.
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!