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

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]

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

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

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

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

Name

Mail (will not be published)

Website

November 15th, 2010 at 03:01

I was actually

notaware of this! Thanks for the links!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

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).

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