Not Yet Answered # Description of the interpolation search algorithm

Black Box 28 domjdragon2 Hey, so I wanna ask how I need to create a method who will remove word if in that word is 2 same chars. Example: "Potato" in this word there is a 2 "o" chars so this word will need to be removed. "Forum" in this word there is no ...

0

> 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

0

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

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

I am writing a java program that needs to execute shell commands, so I wrote a function that would take the command to execute as a string (ie: "mkdir ~/Folder1") and execute that command with the shell. Here is the function:

```
try
{
Runtime run = Runtime.getRuntime();
Process pr = ...
```

Hi. I have a form with list box : lst_product, datagridview : grd_order and button: btn_addline. lst_product has a list of product ids selected from database (MS Acess 2013) , grd_order is by default empty except for 2 headers and btn_addline adds rows to grd_order.

btn_addline :

`Private Sub btn_addline_Click(ByVal ...`