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
*
*
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 = array[start] && key 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));
}
}