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

2019-11-10 22:10:36

字體：大中小

供稿：網(wǎng)友

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

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; } //插值查找其實(shí)與二分主要差別在于公式，每次不是二分了，是根據(jù)公式取的更貼近的一個(gè)值 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.結(jié)果：這里寫圖片描述

斐波那契查找：

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

從圖中可以看出，當(dāng)有序表的元素個(gè)數(shù)不是斐波那契數(shù)列中的某個(gè)數(shù)字時(shí)，需要把有序表的元素個(gè)數(shù)長度補(bǔ)齊，讓它成為斐波那契數(shù)列中的一個(gè)數(shù)值，當(dāng)然把原有序表截?cái)嗫隙ㄊ遣豢赡艿模蝗贿€怎么查找。然后圖中標(biāo)識(shí)每次取斐波那契數(shù)列中的某個(gè)值時(shí)(F[k])，都會(huì)進(jìn)行-1操作，這是因?yàn)橛行虮頂?shù)組位序從0開始的，純粹是為了迎合位序從0開始。所以用迭代實(shí)現(xiàn)斐波那契查找算法如下：

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; // 斐波那契分割數(shù)值下標(biāo) int k = 0; // 序列元素個(gè)數(shù) int i = 0; // 獲取斐波那契數(shù)列 int[] f = fibonacci(); // 獲取斐波那契分割數(shù)值下標(biāo) while (data.length > f[k] - 1) { k++; } // 創(chuàng)建臨時(shí)數(shù)組 int[] temp = new int[f[k] - 1]; for (int j = 0; j < data.length; j++) { temp[j] = data[j]; } // 序列補(bǔ)充至f[k]個(gè)元素 // 補(bǔ)充的元素值為最后一個(gè)元素的值 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]個(gè)元素，由于下標(biāo)從0開始 // 則-1 獲取黃金分割位置元素的下標(biāo) mid = low + f[k - 1] - 1; if (temp[mid] > key) { // 查找前半部分，高位指針移動(dòng) high = mid - 1; // （全部元素） = （前半部分）+（后半部分） // f[k] = f[k-1] + f[k-1] // 因?yàn)榍鞍氩糠钟衒[k-1]個(gè)元素，所以 k = k-1 k = k - 1; } else if (temp[mid] < key) { // 查找后半部分，高位指針移動(dòng) low = mid + 1; // （全部元素） = （前半部分）+（后半部分） // f[k] = f[k-1] + f[k-1] // 因?yàn)楹蟀氩糠钟衒[k-1]個(gè)元素，所以 k = k-2 k = k - 2; } else { // 如果為真則找到相應(yīng)的位置 if (mid <= high) { return mid; } else { // 出現(xiàn)這種情況是查找到補(bǔ)充的元素 // 而補(bǔ)充的元素與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); }}

運(yùn)行結(jié)果：這里寫圖片描述

哈希查找

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

哈希查找的操作步驟：

1) 用給定的哈希函數(shù)構(gòu)造哈希表；

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

3) 在哈希表的基礎(chǔ)上執(zhí)行哈希查找。

建立哈希表操作步驟：

1) step1 取數(shù)據(jù)元素的關(guān)鍵字key，計(jì)算其哈希函數(shù)值（地址）。若該地址對(duì)應(yīng)的存儲(chǔ)空間還沒有被占用，則將該元素存入；否則執(zhí)行step2解決沖突。

2) step2 根據(jù)選擇的沖突處理方法，計(jì)算關(guān)鍵字key的下一個(gè)存儲(chǔ)地址。若下一個(gè)存儲(chǔ)地址仍被占用，則繼續(xù)執(zhí)行step2，直到找到能用的存儲(chǔ)地址為止。

哈希查找步驟為：

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

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

比如說：”5“是一個(gè)要保存的數(shù)，然后我丟給哈希函數(shù)，哈希函數(shù)給我返回一個(gè)”2”，那么此時(shí)的”5“和“2”就建立一種對(duì)應(yīng)關(guān)系，這種關(guān)系就是所謂的“哈希關(guān)系”，在實(shí)際應(yīng)用中也就形成了”2“是key，”5“是value。

那么有的朋友就會(huì)問如何做哈希，首先做哈希必須要遵守兩點(diǎn)原則：

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

②：哈希函數(shù)盡可能的簡(jiǎn)單，也就是說丟一個(gè)“6”給你，你哈希函數(shù)要搞1小時(shí)才能給我，這樣也是不好的。

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

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

很容易理解，key=Value+C；這個(gè)“C”是常量。Value+C其實(shí)就是一個(gè)簡(jiǎn)單的哈希函數(shù)。

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

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

第三種：“數(shù)字分析法”。

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

針對(duì)這樣的數(shù)我們分析數(shù)中間兩個(gè)數(shù)比較波動(dòng)，其他數(shù)不變。那么我們?nèi)ey的值就可以是

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

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

第五種：“折疊法”。

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

影響哈希查找效率的一個(gè)重要因素是哈希函數(shù)本身。當(dāng)兩個(gè)不同的數(shù)據(jù)元素的哈希值相同時(shí)，就會(huì)發(fā)生沖突。為減少發(fā)生沖突的可能性，哈希函數(shù)應(yīng)該將數(shù)據(jù)盡可能分散地映射到哈希表的每一個(gè)表項(xiàng)中。

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

(1) 開放地址法　　

如果兩個(gè)數(shù)據(jù)元素的哈希值相同，則在哈希表中為后插入的數(shù)據(jù)元素另外選擇一個(gè)表項(xiàng)。當(dāng)程序查找哈希表時(shí)，如果沒有在第一個(gè)對(duì)應(yīng)的哈希表項(xiàng)中找到符合查找要求的數(shù)據(jù)元素，程序就會(huì)繼續(xù)往后查找，直到找到一個(gè)符合查找要求的數(shù)據(jù)元素，或者遇到一個(gè)空的表項(xiàng)。　　

(2) 鏈地址法

將哈希值相同的數(shù)據(jù)元素存放在一個(gè)鏈表中，在查找哈希表的過程中，當(dāng)查找到這個(gè)鏈表時(shí)，必須采用線性查找方法。

實(shí)現(xiàn)哈希函數(shù)為“除法取余法”，解決沖突為“開放地址線性探測(cè)法”，代碼如下：

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]; //創(chuàng)建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("已經(jīng)在數(shù)組中找到，索引位置為：" + result); else System.out.println("沒有此原始"); } /**** * Hash表檢索數(shù)據(jù) * * @param hash * @param hashLength * @param key * @return */ public static int searchHash(int[] hash, int hashLength, int key) { // 哈希函數(shù) int hashAddress = key % hashLength; // 指定hashAdrress對(duì)應(yīng)值存在但不是關(guān)鍵值，則用開放尋址法解決 while (hash[hashAddress] != 0 && hash[hashAddress] != key) { hashAddress = (++hashAddress) % hashLength; } // 查找到了開放單元，表示查找失敗 if (hash[hashAddress] == 0) return -1; return hashAddress; } /*** * 數(shù)據(jù)插入Hash表 * * @param hash 哈希表 * @param hashLength * @param data */ public static void insertHash(int[] hash, int hashLength, int data) { // 哈希函數(shù) int hashAddress = data % hashLength; // 如果key存在，則說明已經(jīng)被別人占用，此時(shí)必須解決沖突 while (hash[hashAddress] != 0) { // 用開放尋址法找到 hashAddress = (++hashAddress) % hashLength; } // 將data存入字典中 hash[hashAddress] = data; }}

運(yùn)行結(jié)果：這里寫圖片描述