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