Needle in a haystack in computer science

The slow way: look at everything

If you know nothing about where the needle is, the only choice is to check every piece of hay until you find it. In computer science this is called a linear search. On average you check half of everything before you succeed, and in the worst case you check all of it. It always works, but it takes time in proportion to the size of the pile.

Sorting changes everything

Now imagine the hay is arranged in order, like words in a dictionary. A smarter method, binary search, opens in the middle, decides which half the answer is in, and throws the other half away. Do that again and again and a million items can be searched in about 20 steps. The catch is that the pile must be in order first, and a haystack never is.

Indexes: cheating by preparing

Databases and search engines get around the problem by doing the hard work in advance. They build an index, like the list at the back of a book that tells you which page a word is on. Looking something up becomes quick, because the time was spent earlier. There is no index for a real haystack, which is exactly why the saying exists.

Following a signal

A metal detector is different. It does not tell you where the needle is, but it tells you whether you are getting closer. Imagine a number that goes up as you approach. You can then use a simple rule: take a step, see whether the signal got stronger, and keep going in the direction that improves it. Programmers call a version of this hill climbing, and it powers a lot of practical optimisation.

In the game, the signal is worked out from how far you are from the nearest piece of metal compared to the detector's range. The beeps get faster as that number approaches 1, so your ear performs the hill climb for you. More in How the metal detector works.

When signals fail

Hill climbing can get stuck. If a lot of junk metal is near the needle, the strongest signal may lead you to a nail instead. The game handles this by giving the high-level detectors the ability to tell the needle apart. Real-life searches run into the same problem and use better sensors or extra filters.

The haystack as data

The haystack in the game is itself a data structure: a grid of 88 by 40 by 88 cells, each holding a number for how dense the hay is. Digging means changing numbers, and chunks of 16 cells keep the work small. How that works is in How the haystack works.