はてなブックマーク

The first round of experiments is over, but you can still help out with the second round. Binary search is a wonderful algorithm: theoretically optimal, fast in practice, and discoverable by school children playing guessing games. Usually we think of binary search as being applied to a sorted array, and we teach it this way. It turns out that, because of cache effects, sorted order is usually not