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
60 lines (54 loc) · 2.41 KB
/
Copy pathInterpolationSearch.java
File metadata and controls
60 lines (54 loc) · 2.41 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
package com.search;
public class InterpolationSearch {
/**
* A linear interpolation search algorithm that finds the position of a
* target value in an sorted array using its lowest value and highest value.
*
* Average time-complexity O(log log n) - uniformly distributed.
* Worst-case time-complexity O(n) - non-uniformly distributed
* Worst-case space complexity O(1)
*
* @param <T>This is any comparable type
* @param arr This is the array where the element should be found
* @param key This is the element to find in the array
* @return The index of the key in the array
*/
public <T extends Comparable<T>> int findIndex(T arr[], T key) {
return checkCondition(arr, key, 0, arr.length - 1);
}
/**
* @param lowIndex The first and smallest element in the sorted array
* @param highIndex The last and largest element in the sorted array
* @return The found key's index in the array through iteration
*/
private <T extends Comparable<T>> int checkCondition(T arr[], T key, int lowIndex, int highIndex) {
boolean conditionOne = lowIndex <= highIndex && key.compareTo(arr[lowIndex]) >= 0;
boolean conditionTwo = key.compareTo(arr[lowIndex]) == 0 && key.compareTo(arr[highIndex]) <= 0;
while (conditionOne || conditionTwo) {
int position = getPostion(arr, key, lowIndex, highIndex);
if (arr[position].equals(key))
return position;
if (arr[position].compareTo(key) < 0)
lowIndex = position + 1;
else
highIndex = position - 1;
}
return -1;
}
/**
* @return The array's current retrieved index position
*/
private <T> int getPostion(T arr[], T key, int lowIndex, int highIndex) {
String startValueString = arr[lowIndex].toString(); //First convert <T> array element to String
int startValueInt = Integer.parseInt(startValueString); //Convert String to int to computate later
String endValueString = arr[highIndex].toString();
int endValueInt = Integer.parseInt(endValueString);
String keyValueString = key.toString(); //Repeat for <T> key to later computate
int keyValueInt = Integer.parseInt(keyValueString);
int arrayIndexRangeDiff = highIndex - lowIndex;
int arrayHighLowValuesDiff = endValueInt - startValueInt;
int keyMinusArrayLowValue = keyValueInt - startValueInt;
int position = lowIndex + (((arrayIndexRangeDiff) / (arrayHighLowValuesDiff) * (keyMinusArrayLowValue)));
return position;
}
}