Binary Search http://en.wikipedia.org/wiki/Binary_search_algorithm is a very basic algorithm in computer science. Despite this fact it is also important to understand the fundamental principle behind it. Unfortunately the algorithm is tought so early and the algorithm is so simple that beginning students sometimes have a hard time to understand the abstract principle behind it. Also many exercises are just focused on implementing the algorithm.
I tried to provide an exercise that aims and focusses on the core principle of binara search rather than implementation. The exercise is split into three parts.

Excercise – Binary Search

Your task is to write a computer program that is able to guess your name!

Feel free to check out the following applet that enables my blog to guess your name in less than 16 steps!

In order to achieve this task we will look at three different approaches.

Part 1

• Download this file containing 48’000 names. It is important for me to state that this file is under GNU public licence and I just processed the original much richer file which you can find at: http://www.heise.de/ct/ftp/07/17/182/.
• Now you can apply the binary search algorithm (imperative implementation as well as recursive implementation) to let the computer guess the name of the user
• Provide a small User interface that makes it possible for the user to give feedback if the name would be found befor or after that guess in a telephone book

Part 2

It could happen though that some rare names are not included in this name list. That is why your task now is to use a different approach:

• Let the Computer ask the user of how many letters his name consists.
• Create a function BinarySearch(String from, String to, length) and call it for example with the parameters “(AAAA”,”ZZZZ”,4)
• Use the function LongToString in order to map the String to a Long that respects the lexicographical order and enables to find the middle value of the two strings to implement this
• Use the function LongToString and the user interface from part one in order to provide the output to the user

private static String LongToString(long l,int length) {
String result = "";
for (int i=0;i
private static long StringToLong(String from) {
long result=0;
int length=from.length();
for (int i=0;i

Part 3

Our program from exercise 2 is still not able to guess names with a special charset which is important for many languages. So your task is to fix this problem by improving the approach that you have just implemented.
One way to do this is to understand that char(65)=A, char(66)=B,... and transfer this to create a sorted array of letters that are allowed to be within a name.
Now choose freely one of the following methods:
Method A
Improve LongToString and StringToLong so it can use the array instead of the special characters.
Method B
Start guessing the name letter for letter by using this array. You would guess every letter with the help of binary search.

Part 4 (discussion)

• Explain shortly why approach number 2 will take more guesses in general than approach one.
• Explain shortly why Method A and B will need the same amount of guesses in the worst case.
• If you would already know some letters of the Name does this have an influence on the method you choose. Why?