常見的查找算法（順序、二分、插值、斐波那契查找，哈希查找）

2019-11-11 01:14:47

字體：大中小

來源：轉載

供稿：網友

順序查找、二分查找（非遞歸）、二分查找（遞歸）、插值查找：

public class Search { int SequenceSearch(int[] arr, int value) { for(int i=0; i<arr.length; i++) { if(arr[i] == value) { return i; } } return -1; } int BinarySearch(int[] arr, int value) { int low, high, mid; low = 0; high = arr.length-1; while (low <= high) { mid = (low + high)/2; if(arr[mid] == value) { return mid; } else if(arr[mid] > value) { high = mid - 1; } else if(arr[mid] < value) { low = mid + 1; } } return -1; } int BinarySearchStack(int[] arr, int value, int low, int high) { int mid = low + (high - low)/2; if(arr[mid] == value) { return mid; } else if(arr[mid] > value) { return BinarySearchStack(arr, value, low, mid-1); } else if(arr[mid] < value) { return BinarySearchStack(arr, value, mid+1, high); } return -1; } //插值查找其實與二分主要差別在于公式，每次不是二分了，是根據公式取的更貼近的一個值 int Interpolation(int[] arr, int value, int low, int high) { int mid = low+(value-arr[low])/(arr[high]-arr[low])*(high-low); if(arr[mid]==value) return mid; else if(arr[mid]>value) return Interpolation(arr, value, low, mid-1); else if(arr[mid]<value) return Interpolation(arr, value, mid+1, high); return -1; } public static void main(String[] args) { Search search = new Search(); int[] arr = {20, 14, 25, 11, 6, 2, 5, 19, 35, 42, 55}; System.out.結果：這里寫圖片描述

斐波那契查找：

1、斐波那契查找也叫做黃金分割法查找，它也是根據折半查找算法來進行修改和改進的。 2、對于斐波那契數列：1、1、2、3、5、8、13、21、34、55、89……（也可以從0開始），前后兩個數字的比值隨著數列的增加，越來越接近黃金比值0.618。比如這里的89，把它想象成整個有序表的元素個數，而89是由前面的兩個斐波那契數34和55相加之后的和，也就是說把元素個數為89的有序表分成由前55個數據元素組成的前半段和由后34個數據元素組成的后半段，那么前半段元素個數和整個有序表長度的比值就接近黃金比值0.618，假如要查找的元素在前半段，那么繼續按照斐波那契數列來看，55 = 34 + 21，所以繼續把前半段分成前34個數據元素的前半段和后21個元素的后半段，繼續查找，如此反復，直到查找成功或失敗，這樣就把斐波那契數列應用到查找算法中了。如下圖：這里寫圖片描述

從圖中可以看出，當有序表的元素個數不是斐波那契數列中的某個數字時，需要把有序表的元素個數長度補齊，讓它成為斐波那契數列中的一個數值，當然把原有序表截斷肯定是不可能的，不然還怎么查找。然后圖中標識每次取斐波那契數列中的某個值時(F[k])，都會進行-1操作，這是因為有序表數組位序從0開始的，純粹是為了迎合位序從0開始。所以用迭代實現斐波那契查找算法如下：

public class Search { public static int[] fibonacci() { int[] f = new int[20]; int i = 0; f[0] = 1; f[1] = 1; for (i = 2; i < 20; i++) { f[i] = f[i - 1] + f[i - 2]; } return f; } public static int fibonacciSearch(int[] data, int key) { int low = 0; int high = data.length - 1; int mid = 0; // 斐波那契分割數值下標 int k = 0; // 序列元素個數 int i = 0; // 獲取斐波那契數列 int[] f = fibonacci(); // 獲取斐波那契分割數值下標 while (data.length > f[k] - 1) { k++; } // 創建臨時數組 int[] temp = new int[f[k] - 1]; for (int j = 0; j < data.length; j++) { temp[j] = data[j]; } // 序列補充至f[k]個元素 // 補充的元素值為最后一個元素的值 for (i = data.length; i < f[k] - 1; i++) { temp[i] = temp[high]; } for (int j : temp) { System.out.print(j + " "); } System.out.println(); while (low <= high) { // low：起始位置 // 前半部分有f[k-1]個元素，由于下標從0開始 // 則-1 獲取黃金分割位置元素的下標 mid = low + f[k - 1] - 1; if (temp[mid] > key) { // 查找前半部分，高位指針移動 high = mid - 1; // （全部元素） = （前半部分）+（后半部分） // f[k] = f[k-1] + f[k-1] // 因為前半部分有f[k-1]個元素，所以 k = k-1 k = k - 1; } else if (temp[mid] < key) { // 查找后半部分，高位指針移動 low = mid + 1; // （全部元素） = （前半部分）+（后半部分） // f[k] = f[k-1] + f[k-1] // 因為后半部分有f[k-1]個元素，所以 k = k-2 k = k - 2; } else { // 如果為真則找到相應的位置 if (mid <= high) { return mid; } else { // 出現這種情況是查找到補充的元素 // 而補充的元素與high位置的元素一樣 return high; } } } return -1; } public static void main(String[] args) { Search search = new Search(); int[] data = { 1, 5, 15, 22, 25, 31, 39, 42, 47, 49, 59, 68, 88 }; int value = 39; int position = fibonacciSearch(data, value); System.out.println("值" + value + "的元素位置為：" + position); }}

運行結果：這里寫圖片描述

哈希查找

哈希查找是通過計算數據元素的存儲地址進行查找的一種方法。O(1)的查找，即所謂的秒殺。哈希查找的本質是先將數據映射成它的哈希值。哈希查找的核心是構造一個哈希函數，它將原來直觀、整潔的數據映射為看上去似乎是隨機的一些整數。

哈希查找的操作步驟：

1) 用給定的哈希函數構造哈希表；

2) 根據選擇的沖突處理方法解決地址沖突；

3) 在哈希表的基礎上執行哈希查找。

建立哈希表操作步驟：

1) step1 取數據元素的關鍵字key，計算其哈希函數值（地址）。若該地址對應的存儲空間還沒有被占用，則將該元素存入；否則執行step2解決沖突。

2) step2 根據選擇的沖突處理方法，計算關鍵字key的下一個存儲地址。若下一個存儲地址仍被占用，則繼續執行step2，直到找到能用的存儲地址為止。

哈希查找步驟為：

1) Step1 對給定k值，計算哈希地址 Di=H（k）；若HST為空，則查找失敗；若HST=k，則查找成功；否則，執行step2（處理沖突）。

2) Step2 重復計算處理沖突的下一個存儲地址 Dk=R（Dk-1），直到HST[Dk]為空，或HST[Dk]=k為止。若HST[Dk]=K，則查找成功，否則查找失敗。

比如說：”5“是一個要保存的數，然后我丟給哈希函數，哈希函數給我返回一個”2”，那么此時的”5“和“2”就建立一種對應關系，這種關系就是所謂的“哈希關系”，在實際應用中也就形成了”2“是key，”5“是value。

那么有的朋友就會問如何做哈希，首先做哈希必須要遵守兩點原則：

①: key盡可能的分散，也就是我丟一個“6”和“5”給你，你都返回一個“2”，那么這樣的哈希函數不盡完美。

②：哈希函數盡可能的簡單，也就是說丟一個“6”給你，你哈希函數要搞1小時才能給我，這樣也是不好的。

其實常用的做哈希的手法有“五種”：

第一種：”直接定址法“。

很容易理解，key=Value+C；這個“C”是常量。Value+C其實就是一個簡單的哈希函數。

第二種：“除法取余法”。

很容易理解， key=value%C;解釋同上。

第三種：“數字分析法”。

這種蠻有意思，比如有一組value1=112233，value2=112633，value3=119033，

針對這樣的數我們分析數中間兩個數比較波動，其他數不變。那么我們取key的值就可以是

key1=22,key2=26,key3=90。

第四種：“平方取中法”。此處忽略，見名識意。

第五種：“折疊法”。

這種蠻有意思,比如value=135790，要求key是2位數的散列值。那么我們將value變為13+57+90=160，然后去掉高位“1”,此時key=60，哈哈，這就是他們的哈希關系，這樣做的目的就是key與每一位value都相關，來做到“散列地址”盡可能分散的目地。

影響哈希查找效率的一個重要因素是哈希函數本身。當兩個不同的數據元素的哈希值相同時，就會發生沖突。為減少發生沖突的可能性，哈希函數應該將數據盡可能分散地映射到哈希表的每一個表項中。

解決沖突的方法有以下兩種：　　

(1) 開放地址法　　

如果兩個數據元素的哈希值相同，則在哈希表中為后插入的數據元素另外選擇一個表項。當程序查找哈希表時，如果沒有在第一個對應的哈希表項中找到符合查找要求的數據元素，程序就會繼續往后查找，直到找到一個符合查找要求的數據元素，或者遇到一個空的表項。　　

(2) 鏈地址法

將哈希值相同的數據元素存放在一個鏈表中，在查找哈希表的過程中，當查找到這個鏈表時，必須采用線性查找方法。

實現哈希函數為“除法取余法”，解決沖突為“開放地址線性探測法”，代碼如下：

public class HashSearch { public static void main(String[] args) { //“除法取余法” int hashLength = 13; int [] array = { 13, 29, 27, 28, 26, 30, 38 }; //哈希表長度 int[] hash = new int[hashLength]; //創建hash for (int i = 0; i < array.length; i++) { insertHash(hash, hashLength, array[i]); } int result = searchHash(hash,hashLength, 29); if (result != -1) System.out.println("已經在數組中找到，索引位置為：" + result); else System.out.println("沒有此原始"); } /**** * Hash表檢索數據 * * @param hash * @param hashLength * @param key * @return */ public static int searchHash(int[] hash, int hashLength, int key) { // 哈希函數 int hashAddress = key % hashLength; // 指定hashAdrress對應值存在但不是關鍵值，則用開放尋址法解決 while (hash[hashAddress] != 0 && hash[hashAddress] != key) { hashAddress = (++hashAddress) % hashLength; } // 查找到了開放單元，表示查找失敗 if (hash[hashAddress] == 0) return -1; return hashAddress; } /*** * 數據插入Hash表 * * @param hash 哈希表 * @param hashLength * @param data */ public static void insertHash(int[] hash, int hashLength, int data) { // 哈希函數 int hashAddress = data % hashLength; // 如果key存在，則說明已經被別人占用，此時必須解決沖突 while (hash[hashAddress] != 0) { // 用開放尋址法找到 hashAddress = (++hashAddress) % hashLength; } // 將data存入字典中 hash[hashAddress] = data; }}

運行結果：這里寫圖片描述