forked from vJechsmayr/JavaScriptAlgorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathinterpolation_search.js
More file actions
46 lines (39 loc) · 1.57 KB
/
Copy pathinterpolation_search.js
File metadata and controls
46 lines (39 loc) · 1.57 KB
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
function interpolationSearch(sortedArray, seekElement) {
let leftIndex = 0;
let rightIndex = sortedArray.length - 1;
while (leftIndex <= rightIndex) {
const rangeDelta = sortedArray[rightIndex] - sortedArray[leftIndex];
const indexDelta = rightIndex - leftIndex;
const valueDelta = seekElement - sortedArray[leftIndex];
// If valueDelta is less then zero it means that there is no seek element
// exists in array since the lowest element from the range is already higher
// then seek element.
if (valueDelta < 0) {
return -1;
}
// If range delta is zero then subarray contains all the same numbers
// and thus there is nothing to search for unless this range is all
// consists of seek number.
if (!rangeDelta) {
// By doing this we're also avoiding division by zero while
// calculating the middleIndex later.
return sortedArray[leftIndex] === seekElement ? leftIndex : -1;
}
// Do interpolation of the middle index.
const middleIndex = leftIndex + Math.floor(valueDelta * indexDelta / rangeDelta);
// If we've found the element just return its position.
if (sortedArray[middleIndex] === seekElement) {
return middleIndex;
}
// Decide which half to choose for seeking next: left or right one.
if (sortedArray[middleIndex] < seekElement) {
// Go to the right half of the array.
leftIndex = middleIndex + 1;
} else {
// Go to the left half of the array.
rightIndex = middleIndex - 1;
}
}
return -1;
}
console.log(interpolationSearch([1,2,3,4,5], 3));