Searching random data is not an O(N) problem.

The September/October issue of ACM Queue Magazine has a column I wrote about how to search random data. In theory the best you can do is a linear search. I came up with 10 ways to do better.

http://queue.acm.org/detail.cfm?id=2984631

Computer scientists should be upset that I write these things.