Binary Search

Binary search is a basic algorithm used to locate a desired spot in logarithmic time. It works when you can query whether the answer is higher or lower than your current guess.

For example, say you want to be able to determine my secret number in as few questions as possible. You know that my number is somewhere between \$0\$ and \$2^{31}-1\$ and after each wrong guess you are told whether my number is higher or lower than your guess. Clearly, trying them all would take way too long, but you can get it in just a few questions. Here's how:

The idea is that you want to split the possible range of numbers in half with each question. This is as good as you can do since there are only two answers to each question.

So, your first guess is \$2^{30}\$ - the midpoint of \$0\$ and \$2^{31}-1\$ You are told that my number is lower. You now know that my number is in the range \$[0,2^{30}-1]\$. You then guess the midpoint of this range and continue in this manner. Each time, the range becomes half as large. When there's only one number remaining, that is my number. This will only take about 31 guesses, even with the extraordinarily high bound on the number.

Binary search can also be used to locate an element in a sorted array, or to find the solution to a problem where querying in this manner is much easier than actually solving the problem, such as when a greedy algorithm works in one case but not the other.

page revision: 1, last edited: 05 Jan 2008 04:04
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License