ptnega's technical blog

Interpretation of binary searching algorithm

Problem: Given a random number in range [a, b] (inclusive). What is the maximum number of reasonable attempt the player has to make to get the number?

Let’s start with a more familiar problem: You’ve lost your cow on a rectangular grassland. Assume that the cow is at a fixed position on the land. How would you look for your cow?

This is my idea to find mine if I’m in that situation:

  1. Divide the land by 2, search for the 1st half.
    1. If the cow is there, I search no more.
    2. If it’s not, I will search in the 2nd half. But I will NOT search the whole 2nd half.
      1. I divide it by 2 (again) and search for the 1st new half. If the cow’s there, I search no more,
      2. and if it’s not, I will do the exactly same thing as I’ve done in the previous step.
      3. I will do this again and again until I find my cow. The searching ends when the line I used to divide the land is duplicated with one of those I’ve made in the previous steps. My cow will be on that line 😀

Do you see something that I’ve done the same in each step? Divide the land by 2. It’s exactly the concept of binary searching, that’s why they call it *binary* 😀

Each time you divide the range of searching by 2, you also reduce the time of searching by 2. If your answer is not in this half, then it must be in the other half! The searching ends when you cannot divide the searching range anymore. In other words, “Thisrange” / 2 = “Thisrange” so Thisrange must be zero (You search no more :D)

Each time you divide the range by 2, thus the number of attempts you’ve made is about log2(Range). More specific to say, the number of attempts equals to [log2(Range)] + 1 with [x] is the integral part of x. 2 ^ [log2(Range)] does not guarantee that you’ve searched all in the range. Since you cannot make “half of an attempt” or “quarter of an attempt”, you need to add 1 to your number of attempts.

Of course, that is the answer to the worst case that you need to run to every corner of the land to find your cow. If you’re a bit lucky, you are likely to find your cow in even 3, 2 or just 1 attempt.

To sum up, the maximum number of attempts you need to make to find a random number in range [a, b] is: [log2(b – a + 1)] + 1.

 

Leave a comment »