B4A Class [B4X] [Class] Interpolation search

Short (long-winded ) premise.

I needed a function that, given a list, returned the index of the element with the closest value to a searched one.
List.IndexOf is great but it only returns the index if it finds exactly the searched value.

I immediately thought of a binary search (I remember the good old days, about 45 years ago , when I "studied" the various Bubble, Shell and Quick sort) but I wondered if there was a better algorithm.

I discovered the existence of this "Interpolation search".
The biggest advantage is in the case in which the list of values are uniformly distributed. In the worst case, this algorithm will be as fast as a "normal" binary search.

I publish the function in a class (in the attached project) rather than a library because it will be easier to change the data type of the list, if desired. In my case, I want to pass it a list of custom types (it would be nice to be able to pass it the type and the field to search on, but as far as I know it is impossible).

I hope (and think) that my implementation is correct and optimal.

With the following values:

    For i = 1 To 20
        SortedList.Add(i * 5) ' 5, 10, 15, ..., 100
    Next

 

[Claudio Oliveira]

Well done, Luca!

This thread made me drift back to 1980-something, when I read and "studied" Donald E. Knuth book "The Art Of Computer Programming: Sorting and Searching, Volume 3", which describes and explains all these algorithms mathematically. Fascinating book.
Good old days indeed!

Thanks for sharing.

 

[emexes]

In the worst case, this algorithm will be as fast as a "normal" binary linear search.

 

[LucaMs]

"Good news":

I hope (and think) that my implementation is correct and optimal.

instead it works well only if the list is sorted in ascending order
I'm trying to "refine" it.

 

[LucaMs]

"Good news":



instead it works well only if the list is sorted in ascending order
I'm trying to "refine" it.

It now seems to work fine (I hope ) with both ascending and descending data.

I replaced the project attached to the first post.