-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathbinarySearch_Interpolation.java
More file actions
36 lines (33 loc) · 1.74 KB
/
binarySearch_Interpolation.java
File metadata and controls
36 lines (33 loc) · 1.74 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
/**
* Interpolation search better than binary search
* Referenced from: https://blog.imaginea.com/interpolation-search-a-search-algorithm-better-than-binary-search/
*/
// The difference between the binary and the interpolation sort is that the binary search always splits the the array in half and inspects the middle element.
// Interpolation search calculates a position p, where the value should be placed in accordance to the distribution of values a splits the array at p.
// If the array contains numbers 0, 1, 2, ..., 10 and we are looking for 9 the binary search needs three steps – split at 5, split at 8, split at 9 (found).
// The interpolation search calculates the probable position (index 9) and immediately finds the value.
// Run time: **O(log(logn))**
/**
* Interpolation search
* @param array array with uniformly distributed values in ascending order
* @param value searched value
* @param from first index that might be touched
* @param to last index that might be touched
* @return index index of the searched value in the array, -1 if not found
*/
public static int interpolationSearch(int[] array, int value, int from, int to) {
if(array[from] == value) {
return from;
} else if(from == to || array[from] == array[to]) {
return -1; //not found
}
//probable position of the searched value
int index = from + ((to - from)/(array[to] - array[from])) * (value - array[from]);
if(array[index] == value) {
return index;//found
} else if(array[index] < value) { //continue in the right part of the array
return interpolationSearch(array, value, index + 1, to);
} else { //continue in the left part of the array
return interpolationSearch(array, value, from, index - 1);
}
}