Java数组查找技巧

BNNZ • 2024-11-04 17:51 • 编程

在Java中，数组是一种非常常用的数据结构。在开发中，经常需要对数组进行查找。因此，在本文中，将从多个方面详细阐述Java数组查找技巧。

一、线性查找

线性查找是一种基本的查找方法，也称为顺序查找。顾名思义，它的查找方式就是从数组的头开始，每次逐个元素进行比较，并且在相应的位置找到目标值时返回。这种查找方式适用于无序数组。

/**
 * 线性查找
 * @param arr 数组
 * @param key 待查找关键字
 * @return 返回查找到的位置，未找到返回-1
 */
public static int linearSearch(int[] arr, int key) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == key) {
            return i;
        }
    }
    return -1;
}

二、二分查找

二分查找也称为折半查找，适用于有序数列。它的查找方式是将有序数组分为左右两个部分，每次比较中间位置的元素值，如果匹配则返回，否则缩小查找范围，重复此步骤，直到找到目标值或查找范围为空。

/**
 * 二分查找
 * @param arr 数组
 * @param key 待查找关键字
 * @return 返回查找到的位置，未找到返回-1
 */
public static int binarySearch(int[] arr, int key) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

三、插值查找

插值查找是对二分查找的改进，适用于数值分布比较均匀的有序条件。它的查找方式是根据要查找的关键值key与数组的边界值arr[low]和arr[high]以及中间位置arr[mid]的关系，计算mid的值并且从mid位置开始逐步找到目标值位置。

/**
 * 插值查找
 * @param arr 数组
 * @param key 待查找关键字
 * @return 返回查找到的位置，未找到返回-1
 */
public static int interpolationSearch(int[] arr, int key) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]);
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

四、哈希查找

哈希查找是通过建立一个哈希表来实现查找的方式。哈希表的建立是通过对关键字进行哈希函数的计算，将关键字映射为数组的下标，然后将该关键字存储在对应的数组位置上。在查找时，根据哈希函数计算关键字的位置，判断该位置上的关键字是否匹配，如果匹配，则返回对应数组下标，否则在哈希表中继续查找。

/**
 * 哈希查找
 * @param arr 数组
 * @param key 待查找关键字
 * @return 返回查找到的位置，未找到返回-1
 */
public static int hashSearch(int[] arr, int key) {
    Map map = new HashMap();
    for (int i = 0; i < arr.length; i++) {
        map.putIfAbsent(arr[i], i);
    }
    return map.getOrDefault(key, -1);
}

五、小结

以上就是几种常见的Java数组查找技巧。选择适合自己的查找方法，可以提高查找效率，更好地完成任务。

原创文章，作者：BNNZ，如若转载，请注明出处：https://www.506064.com/n/149145.html