Binary Search – 2
In the previous article we have seen how binary search works. Now we will solve some different problems using the same method. What we will learn now is better known as bisection method.
Let’s see how bisection works to solve a simple problem. Assuming the language you’re programming in doesn’t have a function to find the square root, you’ll have to write the function yourself. We will write a function named mysqrt(X) where we send the number X and return the square root of the number, X can be decimal, but not less than zero.
We won’t go into any complicated math to find the square root, we’ll find the square root by binary search!
Think back to what we were doing when searching for a number in an array sorted from smallest to largest. If the number in the middle is larger, then the right part is omitted, if it is smaller, the left part is omitted.
When taking the square root, we know that the square root of X must be a number between 0 and X. Let X=15. We will take the middle number first. In this case the middle number is 7.5 which when squared again gives 56.25 which is much bigger than 15. That means the square of all other numbers from 7.5 to 15 is greater than 15, we can omit this part.
Now we will again search between 0 and 7.5. The middle number is 3.75 which when squared gives 14.0625 which is less than 15. That means there is no possibility of finding the square root of the division from 0 to 3.75. Now I will search again between 3.75 and 7.5.
I’m not doing the whole simulation by hand, I hope you understand that we’ll keep searching until we find the square root.
If you run this code, you will see that the square root is 3.87296676636 which is squared again to get 14.9998715733. As you can see, due to the problem of decimal precision, the exact answer was not found, but a close answer was found. Line number 4 is very important, here we decide how long we will continue searching, the longer we search the closer we will get to the correct answer. Here we find the difference between high and low until it becomes too small. If you replace the .0001 with a smaller number, you get better results than before. For example using .000000001 gives the square root of 3.87298334594 which when squared again gives 14.9999999979.
If you want, you can specify how many steps the bisection will run.
This time we searched 64 times without thinking about the difference between high and low. Dividing a number by 64 times 2 means shrinking the number drastically, so you’ll get very close to the correct answer. If you want, you can divide 100 or 200 times instead of 64 times for better results, but in that case the runtime of the code will also increase. While determining the number of steps, one should keep in mind how large the high-low value is and also the time limit of the problem.
Many geometry problems can be solved using bisection. Suppose you are given a triangle like the following:
You are given the lengths of AB, AC and BC, and told that DE and BC are parallel. Also, the ratio of the areas of triangle ADE and trapezium BDEC is given by R and u. What is the length of AD?
We can easily solve this by bisection. You assume that the length of AD is x. Now knowing the length of AD, you can easily find out AE, EC, DE using the triangle ratio rule (AD/AB=AE/AC=DE/BC) learned in school. Now you can easily find the area of ADE and BDEC using the length of the side. After knowing the area, find the ratio. If you see that the ratio you get is less than R, then the length x you estimated of AD is less than the actual length. Then you search again in the range from x to high. And if you find that the ratio you get is greater than R, then keep searching in the range from 0 to x. It is your job to figure out how much the value of high will be in the beginning :).
It is very important to understand when bisection will work and when it will not. After learning how to find square roots, you might think that you will solve the equation sin(x)+5*log10(x)=5.27 by bisection. If you assume x=50, then sin(50)+5*log10(50)=9.26. Now can you say for sure that the answer is to the left of 50? Can’t, because if the value of x decreases, the value of sin(x)+5*log10(x) may increase or decrease. Plotting the graph on Google for different values of x gives you:
In this equation, you can’t just do some math on the middle value of a range and cancel out the left or right side, because you have no way of knowing where your answer lies. When taking the square root, the equation is x^2, which is plotted as:
Bisection worked in this case because you could easily discard the left or right side.
There is no need to figure out the plot while solving the problem, I just showed it to you. You can be sure that bisection will work only if a segment can be canceled by looking at the middle value. For example, log(x)+x^2=y can solve this equation by bisection because y always increases as x increases, but tan(x)+x^2=y cannot solve it by bisection.
Now let’s solve a graph problem with bisection. You are given a graph like this:
Each edge is a road with a weight. Now you want to go from A to E in such a way that the maximum weight value on that route is as low as possible. For example, A->B->C->E has a maximum weight of 5, and A->B->E has a maximum weight of 15.
This can easily be solved by bisection. In this case high = 15 at the beginning because the weight of any edge is not more than 15, low = 0, and mid = 7. Now you drop all edges greater than 7 from the graph and see if there is a path from A to G. If not, then the answer to the left of 7 is not possible, discard the left side and search again. Bisection will work in this case because you can cancel the left or right side by looking at the middle value. (This problem can also be solved by slightly modifying Dijkstra’s algorithm instead of bisection.)
You must Join our Facebook Group and Subscribe YouTube Channel
All Links in Below:
Join Our FreeWebsiteCreate Facebook Group to get an instant update for projects, templates, design resources, and solutions.
Join Our YouTube Channel & Subscribe with Bell Icon for New Video:
Join Our Official Facebook Page For the Latest updates All Code Projects are Free:
Visit our service page to get premium services.
You must Join our Facebook Group and Subscribe YouTube Channel