Beating Binary Search

June 17th, 2010

Jay from LinkedIn’s SNA team writes:

Quick, what is the fastest way to search a sorted array?

Binary search, right?

Wrong. There is actually a method called interpolation search

[by Allan Odgaard]

4 Responses to “Beating Binary Search”

  1. Al Says:
    November 15th, 2010 at 03:01

    I was actually not aware of this! Thanks for the links!

  2. Bruce Hoult Says:
    November 21st, 2010 at 04:20

    Note that this is just an array version of the False Position Method vs the Bisection Method for finding roots of a function.

  3. doug Says:
    January 24th, 2011 at 09:36

    my initial impression is that interpolation search is to binary search as A* is related to Dijkstra's (for shortest path).

  4. Christian Wach Says:
    August 20th, 2012 at 06:25

    Try Proxmap Search for O(1)ish Searching

Leave a Reply