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 not aware 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