Binary Search

A search optimized by repeatedly dividing the range to be searched into two not necessarily equal pieces. A single test can then determine that one piece does not contain the value sought, and therefore deemed far less worthy of future attention.

This requires that the search space is ordered. If nothing else is known about the search space, dividing it into two nearly equal pieces is obviously optimal. Knowledge about the search space can be used to bias the choice.

If the smaller piece is always at least as large as some fixed proportion of the space, the algorithm is O(log n).

CommentingChallengeTwo has some fun refactorings of BinarySearch.

A fun description: To catch a lion in the desert.

Cut the desert into two equal halves with a lion-proof fence.
Pick the half which has the lion in it and 
catch the lion in that half of the desert

The algorithm works well only if you can rapidly eliminate half the possibilities. To search in an array, the data must be in order. In a tree, it must be ordered and balanced.

-- DickBotting

Has anyone (other than me) spotted the bug in this yet?

When the fenced-off area is small enough, you stop (deeming the lion to have been caught).

What if the lion leaves the desert?

What if there is no lion? This is usually solved by the "putting a camel in Cairo" technique. In this case, it's a lion, yes, but this works as follows. Have a pet lion, and divide the desert into two - the bit that's close and the bit that's far. Always search the further area first. If you find your own lion, there isn't one there. My wife suggests painting it blue so you know it's the one that isn't there.

Possible bugs - 1) The lion is not atomic, 2) the lion dies because your search is too slow, 3) No fence around the desert.

Split up the work of sorting and searching to get benefit from this algorithm. As an example, I loaded /usr/share/dict/words (already sorted) into a server-side file as a JavaScript array (about 45,000 words). Then I implemented the search client-side to pop up a box of autocompletions. With BinarySearch, the search time is imperceptible when completing on each keypress. With LinearSearch, each keypress takes about 4 seconds to search the array. Go figure.

I would have scaled it up to a larger search space, but the browsers' JavaScript interpreters complained about having to deal with too many literal values in a single file. Spreading the lookup array initialization across files was NotWorthMyTime?.

I am thinking of a number between 1 and 100. What is it?

50? No, too high. 25? No, too low. 37? No, too high. 31? No, too high. 28? Yes!

What's the worst case? Seven tries. Seven comparisons. 2^7-1 = 127, so the original game could be "a number between 1 and 127" instead.

With every comparison, the number of possibilities can be doubled.

I'm thinking of a number between 1 and 65535 ... 16 tries.
I'm thinking of a number between 1 and 1,000,000 ... 20 tries.
I'm thinking of a name in my customer database, which has 4 billion entries ... 32 tries.

For smaller files (for various orders of magnitude of "smaller"), you can simply sort the file.

For larger files, you can just sort the keys. Or you can do a "virtual" sort, and build a tree.

When the file (or table) will fit in memory, as long as you don't have to insert or delete stuff, you can use a straight BinarySearch. If you have to dynamically add/delete stuff, then a linked list or tree will hurt less.

-- Jimi Black

The worst case would use 2^7 = 128. As the numbering starts at 1, there's no need to subtract 1.

I have usually implemented BinarySearch in conjunction with maintaining a sorted array (OrderedCollection). Hence, one often wants both the index where the sought item would be inserted if not found as well as the index of a found item. The ForthLanguage snippet at http://wiki.forthfreak.net/index.cgi?BinarySearchInsertionSort illustrates this kind of utility function (both with and without local variables) which would be used by "insert", "delete", and "find" methods. It assumes items in the array are unique. -- IanOsgood

You haven't yet sent a submission for Coding Challenge ...

Decided not to. I already accept the point of the challenge (UnitTests trump natural language specs) and I'm not interested in the fiddly CornerCase?s for this particular spec (SourGrapes?, admittedly).

That is not actually the entire point of the challenge. You really need to try it before you actually get the full point. Ask DougMerritt.
- Not so; all errors in carefully written code relate to CornerCase?s in the spec or the code (or they would soon be found once the code was put into use), and even if this were somehow an exception, it's absurd to suggest that one can't understand the point by just reading an explanation of it.
A version that has been developed using TestDrivenDevelopment and UnitTests would specifically be very welcome. Please consider this a request.

CategoryAlgorithm