# 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.

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

Full stack android developer | Dhanbad | Bangalore, India

## More from Rajendra Mahato

Full stack android developer | Dhanbad | Bangalore, India