插值查找和斐波那契查找

插值查找（Interpolation Search）

插值查找是一种改进的二分查找，适用于均匀分布的有序数组。它通过预测要查找的值可能的位置来减少搜索次数。

public class InterpolationSearch {
    public static int interpolationSearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right && target >= arr[left] && target <= arr[right]) {
            // 计算插值位置
            int pos = left + ((target - arr[left]) * (right - left)) / (arr[right] - arr[left]);
            
            if (arr[pos] == target) {
                return pos;
            }
            if (arr[pos] < target) {
                left = pos + 1;
            } else {
                right = pos - 1;
            }
        }
        return -1; // 未找到
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50, 60, 70, 80, 90};
        int target = 50;
        int index = interpolationSearch(arr, target);
        System.out.println(index == -1 ? "未找到" : "找到索引: " + index);
    }
}

斐波那契查找（Fibonacci Search）

斐波那契查找基于斐波那契数列来划分搜索区域，适用于数据量大、顺序存储、访问代价较高的场景（如磁盘存储）。

import java.util.Arrays;

public class FibonacciSearch {
    
    // 获取斐波那契数列
    public static int[] fibonacci(int size) {
        int[] fib = new int[size];
        fib[0] = 0;
        fib[1] = 1;
        for (int i = 2; i < size; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return fib;
    }

    public static int fibonacciSearch(int[] arr, int target) {
        int n = arr.length;
        int fibSize = 20; // 预设的斐波那契数列大小
        int[] fib = fibonacci(fibSize);

        // 找到最小的斐波那契数，使其大于等于 n
        int k = 0;
        while (fib[k] < n) {
            k++;
        }

        // 创建扩展数组
        int[] temp = Arrays.copyOf(arr, fib[k]); // 长度扩展至 fib[k]
        for (int i = n; i < fib[k]; i++) {
            temp[i] = arr[n - 1]; // 用最大元素填充
        }

        int left = 0;  // 左边界
        int right = n - 1;  // 右边界

        while (left <= right) {
            int mid = left + fib[k - 2] - 1; // 计算 mid 位置

            if (temp[mid] < target) { 
                left = mid + 1;
                k -= 1; // 右移 k-1
            } else if (temp[mid] > target) {
                right = mid - 1;
                k -= 2; // 左移 k-2
            } else {
                return (mid < n) ? mid : -1; // 防止访问填充部分
            }
        }
        return -1; // 未找到
    }

    public static void main(String[] args) {
        int[] arr = {10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100};
        int target = 50;
        int index = fibonacciSearch(arr, target);
        System.out.println(index == -1 ? "未找到" : "找到索引: " + index);
    }
}

🔹 区别与适用场景

查找方法    适用场景    时间复杂度    额外空间    适合数据
插值查找    数据分布均匀    平均 O(log log n)，最坏 O(n)    O(1)    均匀分布的大规模数据
斐波那契查找    访问代价高的有序数据    O(log n)    O(1)    需要减少访问次数的场景
🎯 总结：

插值查找更快，但对数据分布要求高；

斐波那契查找适用于存储访问成本高的情况，比如磁盘存储。