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: [1]

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.

While driving daughter Jen to school a few years back I noticed she had one of those graphing calculators. She school had given her the use of one for one of her courses. I know it cost only about $50. I said that 30 years ago I had bought one of the first pocket calulators. It was made by Texas Instruments. I said I it only did the four basic functions — add, subtract, multiply and divide — and that it had cost me about $80, but it was still better than an adding machine. She said to me, “Dad, what’s an adding machine?” I said to myself, “Ah, youth.”

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.

Advertisements

2 Comments

  1. Posted April 24, 2007 at 09:52 | Permalink | Reply

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

  2. Posted April 24, 2007 at 09:53 | Permalink | Reply

    correction on E-Mail address

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

  • Pages

  • November 2006
    M T W T F S S
    « Oct   Dec »
     12345
    6789101112
    13141516171819
    20212223242526
    27282930  
  • RSS The Wayward Word Press

  • Recent Comments

    russurquhart1 on SPITBOL for OSX is now av…
    dave porter on On being the maintainer, sole…
    daveshields on On being the maintainer, sole…
    Paul Tallett on On being the maintainer, sole…
    mrrdev on On being the maintainer, sole…
  • Archives

  • Blog Stats

  • Top Posts

  • Top Rated

  • Recent Posts

  • Archives

  • Top Rated

  • %d bloggers like this: