Java數組查找技巧

在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數組查找技巧。選擇適合自己的查找方法，可以提高查找效率，更好地完成任務。