GeezerVison is showing github.com — Java/Programs/InterpolationSearch.java at main · arshcoder13/Java

Expand file tree

InterpolationSearch.java

Copy path

More file actions

Latest commit

History

39 lines (36 loc) · 1.27 KB

InterpolationSearch.java

Copy path

File metadata and controls

39 lines (36 loc) · 1.27 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

// Java program to implement interpolation

public class InterpolationSearch {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int[] arr = {12, 23, 10, 34, 55, 4, 68, 3, 73};

Arrays.sort(arr);

System.out.println("sorted array- " + Arrays.toString(arr));

System.out.println("Enter value to search: ");

int searchElement = sc.nextInt();

int index = interpolationSearch(arr, searchElement);

if(index != -1){

System.out.println("Searched item " + arr[index] + " found at index "+index);

}else{

System.out.println("Searched item " + searchElement + " not found in the array");

}

sc.close();

}

private static int interpolationSearch(int[] arr, int searchElement){

int start = 0;

int end = arr.length - 1;

int position;

while ((arr[end] != arr[start]) && (searchElement >= arr[start]) && (searchElement <= arr[end])) {

position = start + ((searchElement - arr[start]) * (end - start) / (arr[end] - arr[start]));

if (arr[position] < searchElement)

start = position + 1;

else if (searchElement < arr[position])

end = position - 1;

else

return position;

}

if (searchElement == arr[start])

return start ;

else

return -1;

}