Binary Searches

So a mythological interview question supposedly asked by F______k is, "Given the numbers 1 to 1,000, what is the minimum number of guesses needed to find a specific number if you are given the hint 'higher' or 'lower' for each guess you make."

I cannot provide a citation for that question and have not heard it asked myself. It has been passed all around the internet as a 'weird interview question.' This question is indeed not weird at all and you, the programmer, should be able to know how to address this straight away.

A related question I was asked by M_______t was, "When does one use a binary search?" Let me tell you this, the only answer they want to hear for this question is, "When the data is already sorted." Quite obviously, data from 1 to 1000 is already sorted.

So, lets return to the original question and break it down binary style, yo. Lets assume our number is 815. Our independent calculation guesses as follows:

1. Guess: 500
• Response: higher
2. Guess: 750
• Response: higher
3. Guess: 875
• Response: lower
4. Guess: 812
• Response: higher
5. Guess: 843
• Response: lower
6. Guess: 827
• Response: lower
7. Guess: 819
• Response: higher
8. Guess: 815
• Ding

I don't know about you, but this is how I code.

So, we're looking at around eight or nine iterations to find our answer. Although it could be less, what if the number was 500? Obviously it would hit on the first iteration. The question was, "what is the minimum number of guesses needed to find a specific number" so in a literal interpretation of that question would answer, "one".

Anyway, back to binary searches. There is no need for me to define them here as you can and should be able to find that information out yourself. So on to some code! A representation of the above in C++ would be as follows:
int binSearch(int needle, int low, int high) { if (high < low) return -1; // no match int middle = low + ((high - low) / 2); // added debug output for demonstration. cout << "middle: " << middle << " low: " << low << " high: " << high << endl; if (needle > middle) return binSearch(needle, middle, high); else if (needle < middle) return binSearch(needle, low, middle); else return middle; // match }
If called with binSearch(815, 1, 1000) our result would be the following: middle: 500 low: 1 high: 1000 middle: 750 low: 500 high: 1000 middle: 875 low: 750 high: 1000 middle: 812 low: 750 high: 875 middle: 843 low: 812 high: 875 middle: 827 low: 812 high: 843 middle: 819 low: 812 high: 827 middle: 815 low: 812 high: 819
So there you have it.