I recently discovered this article on Colin Wright’s blog about using Binary Search as an interesting test problem: Binary Search Reconsidered.
The algorithm is:
You’re looking for an item in a sorted list, so you look in the middle. If the thing you find is bigger than what you’re looking for, then the item - if it’s there at all - must be in the first half, otherwise it’s in the second half. Repeat until you either find the item, or there are no items left in which case the item is not in the list.
In his book Programming Pearls Jon Bentley wrote that he assigned this problem in courses at Bell Labs and IBM. Professional programmers had a couple of hours to convert the above description into a program in the language of their choice.
At the end of the specified time, almost all the programmers reported that they had correct code for the task … but on testing their code 90% of the programmers found bugs in their programs.
Try writing a program in Lisp to do this. If the number is in the list it should return t:
> (binary-search 5 '(0 1 2 3 5 5 6 7 8 9 10)) t
If the number isn’t in the list it should return nil:
> (binary-search 4 '(0 1 2 3 5 5 6 7 8 9 10)) nil
You’re not allowed to test the program until you’ve finished it.
I wrote my program in uLisp, but I have to admit that my program had a silly mistake so I’m in the 90%. I’ll reveal my answer in this thread in a day or so.
See how well you get on!