java常见算法基本查找

在 Java 中，常见的基本查找算法有以下几种：

线性查找 (Linear Search)：从数组的开头依次比较每个元素，直到找到目标元素或遍历完整个数组。

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1; // 目标元素不存在于数组中
}

二分查找 (Binary Search)：仅适用于已排序的数组，每次将目标元素与数组中间的元素进行比较，不断缩小搜索范围直到找到目标元素或无法缩小范围。

public static 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) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 目标元素不存在于数组中
}

插值查找 (Interpolation Search)：类似于二分查找，但是根据目标元素的估计位置进行搜索。适用于元素分布较为均匀的有序数组。

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;
        } else if (arr[pos] < target) {
            left = pos + 1;
        } else {
            right = pos - 1;
        }
    }
    return -1; // 目标元素不存在于数组中
}

斐波那契查找 (Fibonacci Search)：类似于二分查找和插值查找，但是使用斐波那契数列的长度作为搜索范围，并通过黄金分割比例将搜索范围划分为两部分。

public static int fibonacciSearch(int[] arr, int target) {
    int n = arr.length;
    int fibM2 = 0; // (m-2)th Fibonacci Number
    int fibM1 = 1; // (m-1)th Fibonacci Number
    int fibM = fibM2 + fibM1; // mth Fibonacci Number
    while (fibM < n) {
        fibM2 = fibM1;
        fibM1 = fibM;
        fibM = fibM2 + fibM1;
    }
    int offset = -1; // Offset from the first element
    while (fibM > 1) {
        int i = Math.min(offset + fib-2, n - 1);
    if (arr[i] == target) {
        return i;
    } else if (arr[i] < target) {
        fibM = fibM1;
        fibM1 = fibM2;
        fibM2 = fibM - fibM1;
        offset = i;
    } else {
        fibM = fibM2;
        fibM1 = fibM1 - fibM2;
        fibM2 = fibM - fibM1;
    }
}
if (fibM1 == 1 && arr[offset + 1] == target) {
    return offset + 1;
} else {
    return -1; // 目标元素不存在于数组中
}}

这些算法中，线性查找的时间复杂度为 O(n)，而二分查找、插值查找和斐波那契查找的时间复杂度均为 O(log n)。在特定情况下，插值查找和斐波那契查找可能比二分查找更快，但是它们需要满足一定的前提条件，否则可能会出现较差的性能表现。

此外，Java 中还提供了一些常见的查找算法实现，例如：

Arrays 类中的 binarySearch() 方法：用于在已排序的数组中查找指定元素。

int[] arr = {1, 2, 3, 4, 5};
int index = Arrays.binarySearch(arr, 3);

Collections 类中的 binarySearch() 方法：用于在已排序的集合中查找指定元素。需要注意的是，使用该方法的集合必须实现了 Comparable 接口。

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
int index = Collections.binarySearch(list, 3);

HashMap 类中的 get() 方法：用于根据键查找对应的值。

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
int value = map.get("banana");

TreeMap 类中的 get() 方法：用于根据键查找对应的值。需要注意的是，TreeMap 中的键必须实现了 Comparable 接口。

TreeMap<String, Integer> map = new TreeMap<>();
map.put("apple", 1);
map.put("banana", 2);
int value = map.get("banana");

需要根据具体的场景选择合适的查找算法和数据结构。在选择使用 Java 中提供的查找算法时，需要注意数据的排序和类型要求，否则可能会导致查找结果不准确或抛出异常。

另外，对于大规模数据的查找，还可以使用 Java 中的并行查找算法。Java 并行查找算法基于 Fork/Join 框架实现，可以将查找任务拆分成多个子任务并行执行，以提高查找速度和性能。

Java 并行查找算法包括 Arrays 类中的 parallelPrefix() 和 parallelSetAll() 方法，以及 Stream API 中的 parallel() 方法和 parallelStream() 方法。其中，parallelPrefix() 和 parallelSetAll() 方法用于在数组中执行并行前缀计算和并行赋值操作，可以为后续的查找操作提供支持；而 parallel() 方法和 parallelStream() 方法则可以将集合流或数组流转换成并行流，以便于并行查找操作的执行。

下面是一个使用 parallelStream() 方法进行并行查找的示例代码：

int[] arr = {1, 2, 3, 4, 5};
int target = 3;
OptionalInt result = Arrays.stream(arr)
        .parallel()
        .filter(x -> x == target)
        .findFirst();
if (result.isPresent()) {
    int index = result.getAsInt();
    System.out.println("目标元素在数组中的位置是：" + index);
} else {
    System.out.println("目标元素不存在于数组中");
}

需要注意的是，对于小规模的数据集，使用并行查找算法可能会因为任务拆分和合并的开销而导致性能下降，因此需要根据具体情况选择合适的查找算法和数据结构。

原文链接：codingdict.net

java常见算法基本查找

热门标签