Introduction

Interpolation Search is an improved variant of binary search. It works on the principle of estimating the position of the desired value based on the value being searched and the range of values in the array. This algorithm is efficient for uniformly distributed data.

Algorithm Complexity

The average time complexity of Interpolation Search is O(log log n), while the worst-case time complexity is O(n) when the data is not uniformly distributed.

Program Structure

The Java program consists of the following components:

• InterpolationSearch class: Contains the main logic for the search.
• search method: Implements the interpolation search algorithm.
• main method: Tests the algorithm with a sample array and a target value.

Java Implementation

public class InterpolationSearch {
    
    /**
     * Interpolation search algorithm to find the index of the target value in a sorted array.
     * 
     * @param arr The sorted array in which to search.
     * @param target The value to search for.
     * @return The index of the target value, or -1 if not found.
     */
    public static int search(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high && target >= arr[low] && target <= arr[high]) {
            // Estimate the position of the target
            int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);

            // Check if the target is found
            if (arr[pos] == target) {
                return pos;
            }

            // If target is larger, ignore left half
            if (arr[pos] < target) {
                low = pos + 1;
            }
            // If target is smaller, ignore right half
            else {
                high = pos - 1;
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
        int target = 70;

        int result = search(arr, target);

        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

Explanation of the Code

1. The search method takes a sorted array and the target value as inputs.

2. It initializes low and high pointers to the beginning and end of the array, respectively.

3. Within a while loop, it checks if the target is within the range defined by arr[low] and arr[high].

4. The estimated position pos is calculated using the interpolation formula.

5. If the value at pos matches the target, the index is returned.

6. If the value at pos is less than the target, the low pointer is moved up; otherwise, the high pointer is moved down.

7. If the loop terminates without finding the target, the method returns -1.

Conclusion

Interpolation Search is a powerful algorithm for searching in sorted arrays, particularly when the data is uniformly distributed. By estimating the position of the target value, it can often outperform binary search in practice.