forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathInterpolationSearch.java
More file actions
70 lines (57 loc) · 2.2 KB
/
InterpolationSearch.java
File metadata and controls
70 lines (57 loc) · 2.2 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package Searches;
import static java.lang.String.format;
import java.util.Arrays;
import java.util.Random;
import java.util.stream.IntStream;
/**
* Interpolation search algorithm implementation
*
* <p>Worst-case performance O(n) Best-case performance O(1) Average performance O(log(log(n))) if
* the elements are uniformly distributed if not O(n) Worst-case space complexity O(1)
*
* @author Podshivalov Nikita (https://github.com/nikitap492)
*/
class InterpolationSearch {
/**
* @param array is a sorted array
* @param key is a value what shoulb be found in the array
* @return an index if the array contains the key unless -1
*/
public int find(int array[], int key) {
// Find indexes of two corners
int start = 0, end = (array.length - 1);
// Since array is sorted, an element present
// in array must be in range defined by corner
while (start <= end && key >= array[start] && key <= array[end]) {
// Probing the position with keeping
// uniform distribution in mind.
int pos = start + (((end - start) / (array[end] - array[start])) * (key - array[start]));
// Condition of target found
if (array[pos] == key) return pos;
// If key is larger, key is in upper part
if (array[pos] < key) start = pos + 1;
// If key is smaller, x is in lower part
else end = pos - 1;
}
return -1;
}
// Driver method
public static void main(String[] args) {
Random r = new Random();
int size = 100;
int maxElement = 100000;
int[] integers = IntStream.generate(() -> r.nextInt(maxElement)).limit(size).sorted().toArray();
// the element that should be found
Integer shouldBeFound = integers[r.nextInt(size - 1)];
InterpolationSearch search = new InterpolationSearch();
int atIndex = search.find(integers, shouldBeFound);
System.out.println(
String.format(
"Should be found: %d. Found %d at index %d. An array length %d",
shouldBeFound, integers[atIndex], atIndex, size));
int toCheck = Arrays.binarySearch(integers, shouldBeFound);
System.out.println(
format(
"Found by system method at an index: %d. Is equal: %b", toCheck, toCheck == atIndex));
}
}