Binary search

Discussion in 'Programmer's Corner' started by Cerkit, Jan 5, 2010.

  1. Cerkit

    Thread Starter Senior Member

    Jan 4, 2009
    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.
  2. steveb

    Senior Member

    Jul 3, 2008
    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.
  3. avtanski


    May 29, 2008
    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.
    Last edited: Jan 5, 2010