Can someone explain to me how a binary search works? In context of trying to refine the roots of a function to get more precise values.
Thanks

 

Can someone explain to me how a binary search works? In context of trying to refine the roots of a function to get more precise values.
Thanks

A binary search is a very simple, but powerful search algorithm. If you know that a solution exists between two limits, and if you have a way to test whether a guess is too high or too low, then a binary search can be used.

The binary search works by dividing the range for the answer by 2 on each iteration.

Rather than explain, I'll use an example. Let's say the solution is 0.547, and I don't know that, but know it is between 0 and 1. I start by guessing and checking as follows.

Guess 0.5 ... Answer too low
Guess 0.75 ... Answer too high
Guess 0.625 ... Answer too high
Guess 0.5625 ... Answer too high
Guess 0.53125 ... Answer too low
Guess 0.546875 ... Answer accurate to 3 decimal places

This method is not the fastest converging, in all cases, but it always converges fast enough, and it is guaranteed not to diverge. Hence, it is a very powerful and robust search method.

An example of a binary type of search is the old game of 20 questions. A person thinks of anything and the other person needs to guess what he is thinking by asking 20 questions. A good questioner can usually get the answer. The first question is usually "Animal, vegetable or mineral?", which is three choices, so it's not a perfect "binary" search.

Double precision calculations require at least 50 iterations in a binary search because 2^50 is less than 1e-15, which is the limit of precision for double precision arithmetic.

 

Just wanted to add that I am (and the chances are that you are too) often using binary search when reading paper books. For example, I rarely use bookmarks (mostly I remember the page that I'm on and close the book), but it sometimes happens that I forget the number. A (mostly) binary search works in seconds then. Open to a place where I think I should be in the book; read a few words. If I don't recognize what I'm reading - open the pages in the left hand by splitting in half and try again; else (if I do recognize the text) split the pages in the right hand. It takes just a few tries to get to the right place.

Same thing for dictionaries (paper ones, remember those?) and anything in general that is placed in order.

In rare cases I've used binary search to find my way home, but I'll never try that drink again.