November 13, 2001

You probably know that there are basically two methods to search a value in an array: the brute force approach (i.e. linear searching) and the binary search. Both of them have disadvantages: when the array counts N items, linear searching requires N/2 comparisons on the average for successful searches, and