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

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