Knuth suggests [The Art of Computer Programming, §6.2.1] that interpolation searching is superior to binary searching only for large enough tables (because even random data doesn't have a smooth distribution of values, and because of the arithmetic involved in the interpolation step), and so for the fastest search of an ordered array, you should start with interpolation search and switch over to binary search at some point.
Does your simulation bear this out? (The relative costs of division and memory lookup have changed since Knuth was writing §6.2.1, so it might not be true any more.)
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
no subject
Date: 2009-07-30 19:17 (UTC)Does your simulation bear this out? (The relative costs of division and memory lookup have changed since Knuth was writing §6.2.1, so it might not be true any more.)