Java实现插值查找算法

以下是使用Java实现插值查找算法的代码:

public class InterpolationSearch {

    public static int interpolationSearch(int[] arr, int x) {

        // 获取数组的长度

        int n = arr.length;

        

        // 初始化low和high指针

        int low = 0;

        int high = n - 1;

        while (low <= high && x >= arr[low] && x <= arr[high]) {

            // 如果数组中只有一个元素

            if (low == high) {

                if (arr[low] == x) {

                    return low;

                }

                return -1;

            }

            // 使用插值公式预测位置

            int pos = low + ((high - low) / (arr[high] - arr[low])) * (x - arr[low]);

            // 检查预测位置的元素

            if (arr[pos] == x) {

                return pos;

            }

            if (arr[pos] < x) {

                low = pos + 1;

            } else {

                high = pos - 1;

            }

        }

        return -1;

    }

    public static void main(String[] args) {

        int[] arr = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47};

        int x = 18;

        int result = interpolationSearch(arr, x);

        if (result != -1) {

            System.out.println("元素" + x + "在数组中的索引为" + result);

        } else {

            System.out.println("元素不在数组中");

        }

    }

}



这个示例程序中,interpolationSearch方法接受一个有序数组和目标值,并返回目标值在数组中的索引位置。如果目标值不在数组中,则返回-1。

以下是使用Java实现插值查找算法的代码:

public class InterpolationSearch {

    public static int interpolationSearch(int[] arr, int x) {

        // 获取数组的长度

        int n = arr.length;

        

        // 初始化low和high指针

        int low = 0;

        int high = n - 1;

        while (low <= high && x >= arr[low] && x <= arr[high]) {

            // 如果数组中只有一个元素

            if (low == high) {

                if (arr[low] == x) {

                    return low;

                }

                return -1;

            }

            // 使用插值公式预测位置

            int pos = low + ((high - low) / (arr[high] - arr[low])) * (x - arr[low]);

            // 检查预测位置的元素

            if (arr[pos] == x) {

                return pos;

            }

            if (arr[pos] < x) {

                low = pos + 1;

            } else {

                high = pos - 1;

            }

        }

        return -1;

    }

    public static void main(String[] args) {

        int[] arr = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47};

        int x = 18;

        int result = interpolationSearch(arr, x);

        if (result != -1) {

            System.out.println("元素" + x + "在数组中的索引为" + result);

        } else {

            System.out.println("元素不在数组中");

        }

    }

}



这个示例程序中,interpolationSearch方法接受一个有序数组和目标值,并返回目标值在数组中的索引位置。如果目标值不在数组中,则返回-1。

打赏

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,您说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

分享从这里开始,精彩与您同在