More on binary search

When I first moved to NYC to start my graduate studies I lived in an apartment on the first floor of a building on the North side of West 95th between Broadway and Amsterdam.

A few months into my studies, during afternoon tea on the 13th floor of Warren Weaver Hall, home of the Courant Institute, I fell into a conversation with someone who worked there on the staff. [1] The conversation was as follows:

Me: Hi. … Where do you live?

He: I live on the West Side?

Me: Me too. What street?

He: West 95th.

Me: Me too. Which block?

He: Between Broadway and Amsterdam.

Me: Which building?

He: The one across from the parking garages.

Me: Me too. Which floor?

He: First.

Me: Which apartment?

He: 1A.

Me: I’m in 1D.

I was thankful the exchange ended there. I was starting to think he might be a room-mate I had never met. We had never met because we had different schedules. He worked regular hours, while most classes were held in the evening since so many students worked during the day and took classes part-time. We had different schedules.

The above exchange is an instance of the same technique used in binary searching.

Binary search is also the basis of the parlor game of twenty questions. Someone names something and you are given up to twenty yes/no questions to identify it. So you are exploring a space with 2 * 2 * … * 2 (2 times itself twenty times) or which is 2**12 (a**b stands or a multiplied by itself b times) * 2**8, or 4096 * 256, or about 1,000,000 possibilities.

Here is another example of binary search.

Question: You have a deck of playing cards. You tell me you thinking of one of them. How many yes/no questions does it take to identify which card you’re thinking of?

Answer: There are four suits, each with 13 cards. It takes two questions to find the suit, and 4 questions to find the card (3 questions suffice for 8 while 4 are needed for 16, and 13 is bigger than 8). So it takes 2*4, or at most 6 questions to identify the card.

Well not exactly. It’s a puzzle. Can you see the problem? Think about it before reading the next post, though I know because of the “future is now” effect that you most likely read the answer before you read the question.

Notes:

1. Let’s play Jeopardy, where I give you the answer and you give me the question:

Answer: Mathematics or Physics. Neither department would have the gall to omit an integer. Truth trumps superstition.

Question: Two college departments each have their own building, each with 13 stories. In one building the top floor is #14 while in the other it is #13. Which department is in the second building?

Advertisements

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

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

  • Blog Stats

  • Top Posts

  • Top Rated

  • Recent Posts

  • Archives

  • Top Rated

  • %d bloggers like this: