Description of the interpolation search algorithm

[kiel19]

HOw does interpolation search work, help me with how you end up with log(logN)

[Black Box]

> How does interpolation search work?
Wikipedia explains fairly simply how it works: link.

> Help me with how you end up with log(logN).
Interpolation search is kind of an expansion on binary search because you pick a value, check it with the one you are searching for and based on the outcome, you forget about everything above your picked value or beneath it. Therefor log(n).

As for the double log part I'm not able to proof it mathematically, but here's an intuïtive try.
Instead of just randomly picking a value or picking the one in the middle of your remaining space, you guess where it will be (by using a function of the number of values in between your boundaries, the values of your boundaries and the search value). The outcome of this function is that your next value to compare with might be closer to the lower end or closer to the higher end of the search area.

So by first checking in which part (above or below your picked value) to keep searching and discarding the rest and thereafter deviding that remaining space again you should end up with double log complexity on average.
Worst case remains O(n) though.

Do correct me if I'm wrong.

Hope this helped a little.

Black Box

[domjdragon2]

> How does interpolation search work?
Wikipedia explains fairly simply how it works: link.

> Help me with how you end up with log(logN).
Interpolation search is kind of an expansion on binary search because you pick a value, check it with the one you are searching for and based on the outcome, you forget about everything above your picked value or beneath it. Therefor log(n).

As for the double log part I'm not able to proof it mathematically, but here's an intuïtive try.
Instead of just randomly picking a value or picking the one in the middle of your remaining space, you guess where it will be (by using a function of the number of values in between your boundaries, the values of your boundaries and the search value). The outcome of this function is that your next value to compare with might be closer to the lower end or closer to the higher end of the search area.

So by first checking in which part (above or below your picked value) to keep searching and discarding the rest and thereafter deviding that remaining space again you should end up with double log complexity on average.
Worst case remains O(n) though.

Do correct me if I'm wrong.

Hope this helped a little.

Black Box

You sound right from what Wiki says... But from that it means that it being log(log(n)) is just plain luck i think. I was trying to figure out how to do this to use on a my school project, but i think I'm just ganna go with good old binary which is about the same thing anyway... Just thought of a algorith to do something like this though lol...

See what i just thought of is this

if obj is farther from beg. (u would have to do a special function to figure this out) than the end.
Check the 1/2 - 1 area first maybe?

However this still seems like to much of a pain to me so I'm, like I said, ganna stick with Binary search till i have time to make something better (if I can)