# Interactive Binary Search Game

### How It Works

We're looking for **x** which is a random number from **1** to **72**;

We have to choose from **72 ordered** options;

After each miss, we are told if our miss was **more or less than x**.

We only have **7** guesses to find **x**.

How do we find **x**?

We could guess randomly, but that doesn't seem like a good strategy.

With the right strategy, **we can find x in 7 or fewer guesses every time, guaranteed.**

Let's give it a try.

### The Winning Strategy

We know that our options are **ordered**;

We're told if our misses are more or less than **x**.

Based on these, we can use a **divide and conquer** strategy.

Let's use being told if our misses are more or less than **x** to our advantage,

How? If our miss is **less than x** then all guesses less than our miss are wrong too, and if our miss is **more than x** then all guesses more than our miss are wrong.

We see why this only works when our options are ordered.

We can see that **half-way** through our options is our best first guess.

**Why half-way**?

Half-way allows us to throw away half of our options, we're halving the problem.

What do we do next?

We choose the half-way point or our remaining options.

We repeat this strategy until we're left with only one option.

Our **x** is guaranteed to be one of the half-way guesses.

### What's Luck Got to Do With It

Luck is not a factor in finding **x** in **less than 8** guesses.

Luck is a factor in how many guesses of our 7 that we use

For example, we could get lucky and **x** is the half-way point of our options;

Then we would only use **1** guess, but this was luck.

We are guaranteed to find **x** in **less than 8** guesses, but anything **less than 7** is luck.

It's better to be lucky than good, but we want to be both.

### How Many Guesses Do We Need

The question is - "how many times can we half the number of options before we are left with only one"?

This is a logarithm question, but we don't have to get into that.

Put simply, how many times can we divide our number of options by **2** before we are left with **1** option.

**1.**72/2 = 36

**2.**36/2 = 18

**3.**18/2 = 9

**4.**9/2 = 5 (rounded)

**5.**5/2 = 3 (rounded)

**6.**3/2 = 2 (rounded)

**7.**2/2 = 1

We divide by

**2**because it halves our options.

### Powers of Two

If we are familiar with the **powers of 2**, and we should be, we can easily know the max number of guesses we will need to find an **x** in an ordered set of options?

We just have to find the **power or 2** that is more than or equal to our number of options.

In this case we have **72** which is greater than **64** which is **2 ^{6}** and less than

**128**which is

**2**.

^{7}So more than

**2**and less than

^{6}**2**, this is why we can guarantee that we can find

^{7}**x in 7 guesses**. If we increased our number of options to

**129**, then we would need

**8 guesses**.

If we increased our number of options to

**257**, then we would need

**9 guesses**.

This pattern continues.

Here are the first 10 powers of 2.

^{1}= 2

2

^{2}= 4

2

^{3}= 8

2

^{4}= 16

2

^{5}= 32

2

^{6}= 64

2

^{7}= 128

2

^{8}= 256

2

^{9}= 512

2

^{10}= 1024

### Why Is It Called Binary Search

The word binary tells us there are **2 options**.

What are they?

Each step of our **search** we are halving our options into **2**, keeping one half and discarding the other.

This is why it's called **binary search**.

### Conclusion

Often times in programming binary searches are the best solution.

Beyond programming, we benefit by understanding the strategy of a binary search, this clear, methodical thinking can help us solve all types of problems.

### Resources

- Elements of Programming
- Systematic Programming: An Introduction
- Data-oriented design: software engineering for limited resources and short schedules
- More Effective C++: 35 New Ways to Improve Your Programs and Designs
- From Mathematics to Generic Programming
- Design of Design, The: Essays from a Computer Scientist
- Mythical Man-Month, The: Essays on Software Engineering