Search Algorithm using JAVA — 4

In this article we will get to know about Interpolation Search

Interpolation Search

4. Interpolation Search :

Interpolation search is an improved version of binary search, where the values in a sorted array are uniformly distributed. Interpolation search may go to different location according to the value of the key being search. Binary search always go to the middle element to check.

Example : If the value of the key is closer to the last element, interpolation search is likely to start search toward the end side.

It uses following formula :-

• The idea of formula is to return higher value of pos. [pos means position].
• When element to be searched is closer to arr[hi].
• Smaller value when closer to arr[lo].

pos = lo + (((double)(hi - lo)/(arr[hi] - arr[lo]))*(x-arr[lo]));

Algorithm :

1. In a loop, calculate the value of “pos” using the probe position formula.
2. If it is a match, return the index of the item, and exit.
3. If the item is less than arr[pos], calculate the probe position of the left sub-array. Otherwise calculate the same in the right sub-array.
4. Repeat until a match is found or the sub-array reduces to zero.

Fig : Interpolation Search Algorithm

Code Example :

public class InterpolationSearch {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter the array size");
        int arr_size = scanner.nextInt();
        int[] arr = new int[arr_size];
        System.out.println("Enter the array element");
        for (int i =0; i<arr.length; i++){
            arr[i] = scanner.nextInt();
        }
        System.out.println("Enter a search element");
        int x = scanner.nextInt(); // search element
        int result = interpolationSearch(arr, x);
        if (result != -1){
            System.out.println("element found at index   "+result);
        }else{
            System.out.println("Element not found   " +result);
        }
        scanner.close();
    }

    private static int interpolationSearch(int[] arr, int x) {
        int lo = 0; // initial position
        int hi = (arr.length - 1); // max element in the array
        while(lo <= hi && x >= arr[lo] && x <= arr[hi]){
            if (lo == hi){
                if (arr[lo] == x)
                    return lo;
                    return -1;
            }
            int pos = lo + (((hi - lo)/(arr[hi] - arr[lo]))*(x - arr[lo]));// formula to get position
            if (arr[pos] == x){
                return pos;
            }
            if (arr[pos] < x){
                lo = pos + 1; //new low
            }else{
                hi = pos - 1; //new high
            }
        }
        return -1;

    }
}

In the next article we will get to know about Exponential Search

THANK YOU