## On mathematics: Binary search

As a programmer I live in a binary world. I sometimes count with two fingers, not ten, and to me the powers of 2 – 2, 4, 6, 8, 16, … – come into play often than the powers of ten – 10, 100, 1000 …

Actually there is a flaw in the above. I need just one finger to count in base two. With our ten fingers we can actually express 11 numbers since raising two closed fists denotes zero. (Whether this will require reprinting all our paper currency remains an open question.)

A powerful application of the power of two is the idea of “binary search.”

Suppose you tell me you are thinking of a number between 1 and 1000 and you want to know the smallest number of yes/no questions I can use to tell you that number. Let’s assume you know some mathematics and so are thinkiing of 314, the first few digits of “pi,” which is among other things the ratio of the area of a circle to its diameter. As the mathematically-trained programmer than I am, I ask the following series of questions: 

Me: Is it bigger than or equal to 500?

You: No.

(Now I know it’s less than or equal to 500, and so have eliminated half the possibilities.)

Me: Is it bigger than or equal to 250?

You: Yes

(Similarly, half of the remaining possibilities have been eliminated.)

Me: Is it bigger than or equal to 378? (378 = 250+128)

You: No.

Me: Is it bigger than or equal to 314? (320 = 250+64)

(I’ve just mentioned the number though I don’t yet know it’s the answer.)

You: Yes.

Me: Is it bigger than or equal to 432? (432 = 314 + 128)

You: No.

Me: Is it bigger than or equal to 378? (378 = 314 + 64)

You: No.

Me: Is it bigger than or equal to 346? (346 = 314 + 32)

You: Yes.

Me: Is it bigger than or equal to 318? (314+4)

You: No.

Me: Is it bigger than or equal to 316? (314+2)

You: No.

(Now I know it is 314 or 315.)

Me: Is it 314?

You: Yes.

The net of this is that I find a number using this method with a logarithmic number of questions. In case you don’t remember — or never learned about — logarithms, a short example should suffice. Consider the first four powers of ten:10, 100, 100, 10000. 100 is 10*10, or ten multiplied by ten twice, 1000 is ten multiplied by ten three times, and so on. The logarithms are defined by the number of multiplications and are thus: 1, 2, 3, 4. These are logarithms in base 10.

Logarithms also exist in a programmer’s binary world. The first few powers of two are: 2, 4, 8, 16. The corresponding logarithms, in base 2 and not base 10, are the same: 1, 2, 3, 4.

Before we steam on, since I’m probably giving you more mathematics than you expected, mathematics can also be a source of humor. I heard the following riddle from one of my favorite high-school teachers. His name was Goodsell Slocum and he taught mathematics. Here’s the riddle:

Question: Two squirrels are trapped in a cabin. The cabin is built with logs as is every piece of furniture in it. You come back the next day to find four squirrels. How is that possible?

Answer: They used the log tables to multiply!

To understand this you need to know that you can multiply two numbers by adding their logarithms. For example, 100*100, is 10000, because the log of 100 is 2 and so the log of the result is 4, which gives you 10000.

This is also the idea behind slide rules, but unless you are of a certain age you don’t even know what a slide rule is, so I won’t say about slide rules now.

Speaking about slide rules reminds me of another humorous story.

Back to mathematics.

You can prove that binary search works using a technique called “mathematical induction.” The idea is that you first prove something for one case and suggest a general formula. If you prove that if the formula works for the case n then it also works for n+1 then you have proven that the formula is always true. Let’s try it for binary search:

Theorem: Binary search takes log base-two steps.

Consider the case of just 0 and 1. This takes just one question: “Is it 0?”. So the formula works for 2 numbers since log-base-two of 2 is 1.

Assume for formula is true for n. The case n+1 consists of exactly twice as many numbers, so you just need one additional question: “Is the answer closer to zero than to the largest number” since this question divides the set of numbers into two equal sets, each of size n, and you can then use the method you know works for case n.

The method I used in the proof above, as well as binary search itself, illustrates another common mathematical technique that is often used in programming: Divide and Conquer. You can solve a big problem by dividing it into smaller problems.

So ends the first mathematics lesson. Now we’ll apprly our new knowledge to do some binary searching.

See you in the next post.

Notes.

1. My undergraduate B.S. degree and my M.S. degree were in mathematics; my Ph.D. is in computer science, and getting that also required taking a number of mathematics courses. I’ve forgotten most of what mathematics I learned but hopefully enough remains that I can put together a few posts on this topic.

1. neil

if its not bigger than or equal to 500, then it is smaller than – rather than “less than or equal to”

2. neil

• ### Pages daveshields on SPITBOL for OSX is now av… Russ Urquhart on SPITBOL for OSX is now av… Sahana’s Respo… on A brief history of Sahana by S… Sahana’s Respo… on A brief history of Sahana by S… James Murray on On being the maintainer, sole…