Java实现查找算法的示例代码(二分查找、插值查找、斐波那契查找)

Java实现查找算法的示例代码

在Java中，实现查找算法的方式有很多，包括线性查找、二分查找、插值查找、哈希查找等等。本文将详细讲解Java中实现三种常见的查找算法：二分查找、插值查找、斐波那契查找。

二分查找

二分查找也称为折半查找，是一种效率较高的查找算法。二分查找的条件是数据必须是有序的，每次查找都是将查找区间缩小一半，直到查找到目标或者查找区间为空为止。

二分查找的实现可以采用循环或递归的方式，下面是二分查找的示例代码：

public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

示例说明：

在上面的代码中，首先定义了左右两个指针left和right，表示查找区间的左右两端。在每一次查找过程中，计算出mid=left+(right-left)/2表示中间位置，然后通过比较mid和target的大小，将查找区间缩小一半。如果arr[mid]target，则在左半区间查找，即将右指针right移动到mid-1位置。如果arr[mid]==target，则找到目标，返回mid。

插值查找

插值查找是对二分查找的改进，它是根据查找值在数组中的大致位置进行估算，从而缩小查找区间。如果数组中的元素分布比较均匀，那么插值查找的效率会比二分查找更高。

插值查找的实现也可以采用循环或递归的方式，下面是插值查找的示例代码：

public int interpolationSearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) * (target - arr[left]) / (arr[right] - arr[left]);
        if (arr[mid] < target) {
            left = mid + 1;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

示例说明：

在上面的代码中，首先定义了左右两个指针left和right，表示查找区间的左右两端。在每一次查找过程中，计算出mid=left+(right-left)*(target-arr[left])/(arr[right]-arr[left])，表示平均分配，因此可以将查找区间近似看作等差数列，从而可以比较平均地猜测目标元素所在的位置。然后通过比较mid和target的大小，将查找区间缩小。如果arr[mid]target，则在左半区间查找，即将右指针right移动到mid-1位置。如果arr[mid]==target，则找到目标，返回mid。

斐波那契查找

斐波那契查找是利用斐波那契数列进行查找的一种方法，与二分查找和插值查找不同，它不是通过平均分配的方式来确定查找点，而是利用黄金分割原理来确定查找点。

斐波那契查找的实现可以采用递归或非递归的方式，下面是斐波那契查找的示例代码：

public int fibonacciSearch(int[] arr, int target) {
    int n = arr.length;
    int k = 0;
    while (fibonacci(k + 1) - 1 < n) k++;
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + fibonacci(k - 1) - 1;
        if (arr[mid] < target) {
            left = mid + 1;
            k -= 2;
        } else if (arr[mid] > target) {
            right = mid - 1;
            k--;
        } else {
            return mid;
        }
    }
    return -1;
}

private int fibonacci(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    int a = 0, b = 1;
    int res = 0;
    for (int i = 2; i <= n; i++) {
        res = a + b;
        a = b;
        b = res;
    }
    return res;
}

示例说明：

在上面的代码中，首先定义了斐波那契数列，在计算出n<=斐波那契数列第k个数的最大下标k后，初始化左右两个指针left和right，表示查找区间的左右两端。在每一次查找过程中，计算mid=left+fibonacci(k-1)-1，其中fibonacci(k-1)-1用来确定黄金分割点，并将查找区间缩小。如果arr[mid]target，则在左半区间查找，即将右指针right移动到mid-1位置，并且k=k-1；如果arr[mid]==target，则找到目标，返回mid。

以上三种查找算法都是较常用的查找算法，特别是在大数据量、组织有序时，查找算法的效果更为明显。