its101.md.wk.08.09.InterpolationSearch

package its101.mdwk08_09;

import java.util.Arrays;

public class InterpolationSearch {

    //    Create function interpolationSearch()
    public static int interpolationSearch(int[] array, int lo, int hi, int key) {

        if (lo <= hi && key >= array[lo] && key <= array[hi]) {

            // Probing position while keeping the distribution uniform
            int mid = lo + (((hi - lo) / (array[hi] - array[lo])) * (key - array[lo]));
            // If key or target is found return the index position
            if (array[mid] == key) {
                return mid;
            }
            // If key is larger than mid point, key is in the right sub array
            if (array[mid] < key) {
                return interpolationSearch(array, mid + 1, hi,
                        key);
            }
            // If key is smaller than mid point, key is in the left sub array
            if (array[mid] > key) {
                return interpolationSearch(array, lo, mid - 1,
                        key);
            }
        }
        //  Return -1 if key is not found in the array
        return -1;
    } //    End of function interpolationSearch()

    public static void main(String[] args) {

//        A
        // Create array
        int[] arrayA = {2, 3, 5, 7, 9};
        //  Set hi (upper bound)
        int hi = arrayA.length - 1;

        // Print array arrayA
        System.out.println(Arrays.toString(arrayA));

        // Initiate element key1 to be search
        int key1 = 7;
        // Initiate the search result1 using the interpolationSearch() function
        int result1 = interpolationSearch(arrayA, 0, hi, key1);

        // If-else statement for printing the result1
        if (result1 != -1) {
            System.out.println("Element " + key1 + " is present at index " + result1);
        } else {
            System.out.println("Element " + key1 + " is not present in the array");
        }

        System.out.println();

//        B
        // Create new array
        int[] arrayB = {1, 4, 5, 8, 9};
        //  Set hi (upper bound)
        int hi2 = arrayB.length - 1;

        // Print array
        System.out.println(Arrays.toString(arrayB));

        // Initiate element key2 to be search
        int key2 = 2;
        // Initiate the search result2 using the interpolationSearch() function
        int result2 = interpolationSearch(arrayB, 0, hi2, key2);

        // If-else statement for printing the result1
        if (result2 != -1) {
            System.out.println("Element " + key2 + " is present at index " + result2);
        } else {
            System.out.println("Element " + key2 + " not found");
        }
    }
}