SIGPIPE 13

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.

    http://en.wikipedia.org/wiki/False_position_method

  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 http://en.wikipedia.org/wiki/Proxmap_sort#Proxmap_Searching

    http://dl.acm.org/citation.cfm?id=1113847.1113874&coll=DL&dl=GUIDE&CFID=144061613&CFTOKEN=74273107 http://dl.acm.org/citation.cfm?id=1138403.1138427&coll=DL&dl=GUIDE&CFID=144061613&CFTOKEN=74273107


Leave a Reply