|
在Java中，常用的查找算法有以下四種： 一、順序查找順序查找非常簡(jiǎn)單，就是遍歷數(shù)組，找到了就返回元素下標(biāo)，代碼如下： public static int find(int[] arr, int targetNum){
if (arr == null) {
return -1;
}
for (int i = 0; i < arr.length; i++) {
if (arr[i] == targetNum){
return i;
}
}
return -1;
}
二、二分查找二分查找又叫折半查找，首先二分查找的數(shù)列是要有序的，如果無序就不能用二分查找。 1. 二分查找思路： - 首先確定該數(shù)組的中間下標(biāo)，`mid = (left + right) / 2；
- 然后讓
arr[mid]和要和查找的元素比較，如果要查找的元素更大，說明應(yīng)該向右查找，反之向左； - 將左(右)邊當(dāng)成一個(gè)新數(shù)組，重復(fù)第一第二步，即進(jìn)行遞歸。找到了就結(jié)束遞歸，或者遍歷完了數(shù)組也沒找到也結(jié)束遞歸。
2. 代碼實(shí)現(xiàn)： public static int find(int[] arr, int left, int right, int targetNum){
if (left > right){
return -1;
}
int mid = (left + right) / 2;
if (arr[mid] > targetNum) {
return find(arr, left, mid - 1, targetNum);
} else if (arr[mid] < targetNum){
return find(arr, mid + 1, right, targetNum);
} else {
return mid;
}
}
三、插值查找插值查找也是二分查找，不同的是，mid的計(jì)算公式不再是mid = (left + right) / 2，變成了mid = left + (targetNum- arr[left]) / (arr[right] - arr[left]) * (right -left)，其他的都和二分查找一樣。這個(gè)mid的計(jì)算公式是大佬發(fā)明的，大家有興趣可以用數(shù)學(xué)推導(dǎo)一下。 四、斐波那契查找斐波那契查找又叫黃金分割查找，黃金分割是初中學(xué)習(xí)的內(nèi)容，之后又學(xué)習(xí)了斐波那契數(shù)列。 1, 1, 2, 3, 5, 8, 13……
這個(gè)就是斐波那契數(shù)列，相鄰兩個(gè)數(shù)的比值無限接近黃金分割值0.618。斐波那契查找就是利用斐波那契數(shù)列的這個(gè)特性來設(shè)計(jì)的查找算法。 1. 斐波那契查找介紹： 斐波那契查找和二分查找、插值查找也類似，數(shù)組也要是有序的。不同之處還是mid的計(jì)算方法。公式為：mid = left + f(k-1) - 1。對(duì)于這個(gè)公式做幾點(diǎn)說明： 斐波那契數(shù)列是符合f(k) = f(k-1) + f(k-2)的一個(gè)數(shù)列，例如1, 1, 2, 3, 5, 8……； 要使用斐波那契查找，就要先構(gòu)建一個(gè)斐波那契數(shù)列，用來獲取中間索引mid； 斐波那契數(shù)列的長(zhǎng)度就和原始數(shù)組保持一致即可； left表示原始數(shù)組左邊索引，初始的時(shí)候就是0，構(gòu)建好斐波那契數(shù)組，我們要讓f(k-1) - 1指向數(shù)組的最后一個(gè)索引；
然后從斐波那契數(shù)組中根據(jù)mid = left + f(k-1) - 1來獲取中間索引； 然后創(chuàng)建一個(gè)新數(shù)組，長(zhǎng)度為f(k)，因?yàn)殚L(zhǎng)度為f(k)的數(shù)組才滿足f(k) = f(k-1) + f(k-2)，才能使用斐波那契數(shù)列去獲取mid索引。將原始數(shù)組的所有數(shù)拷貝過去，如果f(k)的值大于原始數(shù)組的長(zhǎng)度，那就就將超出長(zhǎng)度的部分用原始數(shù)組的最后一個(gè)數(shù)填充； 根據(jù)mid索引去上面創(chuàng)建的新數(shù)組中獲取元素進(jìn)行比較； 如果這個(gè)數(shù)比要查找的數(shù)更小，那說明在原始數(shù)組的mid的左邊，那就讓right = mid - 1，同時(shí)k要減1，因?yàn)閯偛盼覀兪窃陟巢瞧鯏?shù)列f(k)的位置獲取的索引，在f(k)的前面，有f(k-1)個(gè)元素，將這個(gè)f(k-1)個(gè)元素繼續(xù)拆分，就可以拆成f(k-1) = f(k-2) + f(k-3)，再根據(jù)mid = left + f(k-1-1) - 1重新獲取mid； 如果這個(gè)數(shù)比要查找的數(shù)更大，就讓left = mid + 1，同時(shí)k要減2，因?yàn)樯厦嬲f了，斐波那契數(shù)列滿足f(k) = f(k-1) + f(k-2)，在f(k)的左邊，有f(k-1)個(gè)元素，右邊有f(k-2)個(gè)元素，繼續(xù)拆分就變成了f(k-2) = f(k-3) + f(k-4)，所以是k-2，再根據(jù)mid = left + f(k-1-2) - 1重新獲取mid； 如果mid對(duì)應(yīng)是數(shù)剛好等于被查找數(shù)，那說明找到了，mid索引就是就被查找元素的位置，但是不能直接返回mid，因?yàn)樯厦嬲f了，f(k)可能比原始數(shù)組長(zhǎng)度更長(zhǎng)，超出部分用原始數(shù)組最后一個(gè)元素填充，如果直接返回mid，此時(shí)mid可能指向的是超出部分的元素，用這個(gè)mid去原始數(shù)組中找，就越界了，所以應(yīng)該返回mid和right中較小的那個(gè)。
2. 代碼實(shí)現(xiàn)： public static int find(int[] arr, int targetNum){
int left = 0; // 原始數(shù)組最左邊的下標(biāo)
int right = arr.length - 1; // 原始數(shù)組最右邊的下標(biāo)
int k = 0; // 表示斐波那契分割數(shù)值的下標(biāo)
int mid = 0; // 初始化mid為0
// 獲取到斐波那契數(shù)列
int[] f = fib(arr.length);
// 讓f(k) - 1指向數(shù)組的最后一個(gè)索引
while (f[k] - 1 < right){
k++;
}
// 但是f(k)不是步長(zhǎng)為1的遞增數(shù)列，所以可能出現(xiàn) f(k) - 1 的值大于原始數(shù)組最后一個(gè)索引的情況
// 比如原始數(shù)組最大索引為4，那么此時(shí)f(k)就等于5，所以需要構(gòu)造一個(gè)新數(shù)組，長(zhǎng)度不夠的部分會(huì)用0填充
int[] temp = Arrays.copyOf(arr, f[k]);
// 將Arrays.copyof()方法填充的0用原始數(shù)組最后一個(gè)數(shù)填充
for (int i = right + 1; i < temp.length; i++) {
temp[i] = arr[right];
}
// 循環(huán)查找targetNum
while (left <= right){
mid = left + f[k-1] - 1;
if (targetNum < temp[mid]){ // 向左查找
right = mid - 1;
k--;
} else if (targetNum > temp[mid]){ // 向右查找
left = mid + 1;
k -= 2;
} else { // 返回mid和right中較小的值
return mid <= right ? mid : right;
}
}
return -1;
}
/**
* 得到一個(gè)斐波那契數(shù)列
* @return
*/
public static int[] fib(int length){
int[] fibArr = new int[length];
fibArr[0] = 1;
fibArr[1] = 1;
for (int i = 2; i < length; i++) {
fibArr[i] = fibArr[i-1] + fibArr[i-2];
}
return fibArr;
}
|
