forked from jainaman224/Algo_Ds_Notes
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Interpolation_Search.js
47 lines (31 loc) · 909 Bytes
/
Interpolation_Search.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// Function for Interpolation search
function Interpolation_Search(array, search_item)
{
var low = 0;
var high = array.length - 1;
var pos;
while (low <= high && search_item >= array[low] && search_item <= array[high])
{
var rise = high - low;
var run = array[high] - array[low];
var x = search_item - array[low];
pos = low + Math.floor(rise / run) * x;
if (array[pos] === search_item)
return pos;
else if (search_item < array[pos])
high = pos - 1;
else if (search_item > array[pos])
low = pos + 1;
}
return -1;
}
var array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
var search_item = 5;
var index = Interpolation_Search(array, search_item);
if (index !== -1)
console.log("found at position " + (index + 1));
else
console.log("Not found");
/* Output
Found at position 5
*/