算法-查找算法

下面是使用 Java 实现的四种查找算法：

1. 线性查找（Linear Search）
2. 二分查找（Binary Search）
3. 插值查找（Interpolation Search）
4. 斐波那契查找（Fibonacci Search）

✅ 1. 线性查找（Linear Search）

说明：

从数组的第一个元素开始，逐个比较，直到找到目标值或遍历完整个数组。

Java 实现：

public class LinearSearch {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i; // 返回索引
            }
        }
        return -1; // 未找到
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 7, 1, 9, 3};
        int target = 7;
        System.out.println("Index of " + target + ": " + linearSearch(arr, target)); // 输出 2
    }
}

✅ 2. 二分查找（Binary Search）

说明：

适用于有序数组。每次将查找区间缩小一半，效率高，时间复杂度为 O(log n)。

Java 实现：

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        int target = 7;
        System.out.println("Index of " + target + ": " + binarySearch(arr, target)); // 输出 3
    }
}

✅ 3. 插值查找（Interpolation Search）

说明：

是对二分查找的优化，适用于数据分布均匀的有序数组。通过插值公式计算中间点，平均性能优于二分查找。

Java 实现：

public class InterpolationSearch {
    public static int interpolationSearch(int[] arr, int target) {
        int left = 0;
        int 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;
            } else 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, 100};
        int target = 60;
        System.out.println("Index of " + target + ": " + interpolationSearch(arr, target)); // 输出 5
    }
}

✅ 4. 斐波那契查找（Fibonacci Search）

说明：

基于斐波那契数列对数组进行分割，也是一种适用于有序数组的查找算法，平均性能与二分查找相当，但减少除法运算，在某些硬件环境下效率更高。

Java 实现：

public class FibonacciSearch {
    public static int fibonacciSearch(int[] arr, int target) {
        int n = arr.length;
        int[] fib = new int[20];
        fib[0] = 0;
        fib[1] = 1;
        int i = 1;
        while (fib[i] < n) {
            fib[++i] = fib[i - 1] + fib[i - 2];
        }

        int offset = 0;
        while (fib[i] > 1) {
            int k = Math.min(offset + fib[i - 2], n - 1);

            if (arr[k] < target) {
                offset = k;
                fib[i] = fib[i - 1];
                fib[i - 1] = fib[i - 2];
                i--;
            } else if (arr[k] > target) {
                fib[i] = fib[i - 2];
                fib[i - 1] = fib[i - 1] - fib[i - 2];
                i--;
            } else {
                return k;
            }
        }

        if (fib[i - 1] == 1 && arr[offset + 1] == target) {
            return offset + 1;
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
        int target = 9;
        System.out.println("Index of " + target + ": " + fibonacciSearch(arr, target)); // 输出 4
    }
}

✅ 查找算法对比表

✅ 总结

• 线性查找：最简单，但效率低，适合小数据或无序数组。
• 二分查找：最常用，适用于有序数组，效率高。
• 插值查找：适用于数据分布均匀的场景，性能优于二分查找。
• 斐波那契查找：减少除法操作，适合某些硬件环境，实现稍复杂。

在实际开发中，根据数据是否有序、数据分布、性能需求等选择合适的查找算法。