Java有序表查找：折半查找、二分查找、差值查找和斐波那契查找

? ? 【尊重原創，轉載請注明出處】http://blog.csdn.net/guyuealian/article/details/51106238 ? ? ?目前查找方法主要：順序查找、有序查找（分為：折半查找即二分查找、差值查找和斐波那契查找方法）、線性索引查找、二叉排序樹、平衡二叉樹（AVL樹）以及多路查找樹（B樹）、散列表查找（哈希表）等查找方法 ? ? ?【1】順序查找：是最簡單的查找方法，其時間復雜度為O(n)，是通過構造一個線性表，采用遍歷的方法，將記錄與關鍵字一個一個的對比，若相等則查找成功，若全都不相等，則查找失敗即記錄不存在； ? ? ?【2】有序查找：順序表的記錄一般是無序，而有序表的記錄是有序的；使用有序表查找方法時，前提條件是待查找的記錄必須是已經排好序的。?有序查找分為：折半查找即二分查找、差值查找和斐波那契查找方法
? ? ? （1）折半查找法：又稱二分查找，是最經典的有序表查找，它的前提是線性表中的記錄必須是有序的（通常從小到大排列），線性表采用順序存儲的方式；其基本思路是：將關鍵字key與中間記錄（（low+high）/2）進行比較；若相等，則查找成功；若關鍵字小于中間記錄，則說明關鍵字可能在下半區；若大于，則說明關鍵字可能在上半區；不斷重復上述過程，直到查找成功或失敗； ? ? ? ?Java代碼如下： package javatest1; public class JavaTest1 {public static void main(String[] args) {int[] num = { 1, 2, 3, 4, 5, 6 };//必須有序int index = Binary_Search(num, 5);System.out.print(index);}/* num：有序表（由小到大排列）* key：要查找的關鍵字* return：還回查找到關鍵字的下標，沒有找到則還回-1*/private static int Binary_Search(int[] num, int key) {int low, high, mid;low = 0;high = num.length - 1;while (low <= high) {mid = (low + high) / 2;if (key < num[mid])high = mid - 1;else if (key > num[mid])low = mid + 1;else// 如果等于則直接還回下標值return mid;}return -1;} } ? ? ? （2）插值查找：對二分法查找進行改進，將要查找的關鍵字key與查找表中的最大最小值記錄進行比較后，再確定查找的范圍。在二分法查找中，是以中間記錄作為查找分區的，即將表一分為二，分為上下兩個查找分區： ? ? ? 而插值查找采用插值公式的方法，來確定查找分區。可簡單這樣理解，比如有100個數其值在0~1000范圍之間從小到大排序，你要查找關鍵字為5的位置下標，若采用二分法，則大概在500的地方往下查找，但采用插值的方法，可以通過插值計算出5這個關鍵字應該在靠近0的地方，因此查找時從50往下開始查找，從而提高效率：

? ? ? 因此插值查找只需要在折半查找算法的代碼中簡單修改一下即可： package javatest1; public class JavaTest1 {public static void main(String[] args) {int[] num = { 1, 2, 3, 4, 5, 6 };// 必須有序int index = Insert_Search(num, 5);System.out.print(index);}/** num：有序表（由小到大排列） key：要查找的關鍵字 return：還回查找到關鍵字的下標，沒有找到則還回-1*/private static int Insert_Search(int[] num, int key) {int low, high, mid;low = 0;high = num.length - 1;while (low <= high) {// mid = (low + high) / 2;//二分查找mid = low + (high - low) * (key - num[low])/ (num[high] - num[low]); // 插值查找if (key < num[mid])high = mid - 1;else if (key > num[mid])low = mid + 1;else// 如果等于則直接還回下標值return mid;}return -1;} }

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的Java有序表查找：折半查找、二分查找、差值查找和斐波那契查找的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。