1）順序查找或叫線性查找

就是順序遍歷匹配

2）二分查找

package search;public class BinarySearch {/*** 二分查找數(shù)組必須有序*//**** @param arr 數(shù)組* @param left 左邊索引* @param right 右邊索引* @param findVal 要查找的值* @return 找到就返回，找不到返回-1*/public static int binarySearch(int [] arr, int left, int right, int findVal){int mid = (left + right)/2;int midVal = arr[mid];if (left > right){ //說(shuō)明沒(méi)有找到return -1;}if (findVal > midVal){ //向右遞歸return binarySearch(arr,mid + 1,right,findVal);} else if (findVal < midVal ){ // 向左遞歸return binarySearch(arr, left,mid - 1,findVal);}else { //找到return mid;}}public static void main(String []args){int arr [] = {1,2,3,4,5,6,7,8,9};System.out.println(binarySearch(arr,0,arr.length-1,20));} }

那么如果有多個(gè)相同的數(shù)，怎么全部都找出來(lái)？

就是在找到值后，先不返回加入到ArrayList，而是向左向右掃描是否有一樣的，有就加入到ArrayList。最后再返回ArrayList，沒(méi)找到返回一個(gè)空的ArrayList。

package search;import java.util.ArrayList;public class BinarySearch {public static ArrayList<Integer> arrayList = new ArrayList<>();public static ArrayList<Integer> binarySearch1(int [] arr, int left, int right, int findVal){int mid = (left + right)/2;int midVal = arr[mid];if (left > right){ //沒(méi)找到返回一個(gè)空的集合，根據(jù)size就可以判斷return new ArrayList<>();}if (findVal > midVal){ //向右遞歸return binarySearch1(arr,mid + 1,right,findVal);}else if(findVal < midVal){ //向左遞歸return binarySearch1(arr,left,mid - 1, findVal);}else {/*** 思路分析* 1. 找到mid索引值不直接返回* 2. 向mid索引值的左邊掃描，與midVal一樣就把下標(biāo)存到ArrayList* 3. 向mid索引值的右邊掃描，與midVal一樣就把下標(biāo)存到ArrayList* 4. 將ArrayList返回*///1.找到mid索引值不直接返回,而是加到ArrayList里arrayList.add(mid);//2. 向mid索引值的左邊掃描，與midVal一樣就把下標(biāo)存到ArrayListint temp = mid - 1;while(temp >= 0 && arr[temp] == findVal){arrayList.add(temp);temp--;}//3. 向mid索引值的右邊掃描，與midVal一樣就把下標(biāo)存到ArrayListtemp = mid + 1;while (temp <= arr.length-1 && arr[temp] == findVal){arrayList.add(temp);temp++;}}//4.返回ArrayListreturn arrayList;}public static void main(String []args){int arr [] = {1,2,3,4,5,6,7,8,9,9,9};ArrayList<Integer> arrayList = binarySearch1(arr, 0, arr.length - 1, 9);System.out.println(arrayList.size());arrayList.forEach(System.out::println);} }

3)插值查找（把二分查找的mid進(jìn)行自適應(yīng)優(yōu)化）

分布不均勻的話不一定比折半好

package search;public class InsertValSearch {static int i = 1;public static int insertValSearch(int [] arr, int left, int right, int findVal){System.out.println("調(diào)用第" + i++ + "次");//注意findVal < arr[0] || findVal > arr[arr.length-1]必須有，否則mid可能會(huì)越界if (left > right || findVal < arr[0] || findVal > arr[arr.length-1]){return -1;}int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);int midVal = arr[mid];if (findVal > midVal){return insertValSearch(arr,mid + 1,right,findVal);}else if (findVal < midVal){return insertValSearch(arr,left,mid - 1,findVal);}else {return mid;}}public static void main(String[] args) {int [] arr = new int[100];//int [] arr1 = {1, 8, 10, 89, 1000, 1234};for (int i = 0; i < 100; i++) {arr[i] = i + 1;}int index = insertValSearch(arr, 0, arr.length - 1, 80);System.out.println("index = "+ index);//System.out.println(Arrays.toString(arr));} }

4）斐波那契查找（黃金分割法1:1.618）

對(duì)于斐波那契數(shù)列：1、1、2、3、5、8、13、21、34、55、89……，前后兩個(gè)數(shù)字的比值隨著數(shù)列的增加，越來(lái)越接近黃金比值0.618。比如這里的89，把它想象成整個(gè)有序表的元素個(gè)數(shù)，而89是由前面的兩個(gè)斐波那契數(shù)34和55相加之后的和，也就是說(shuō)把元素個(gè)數(shù)為89的有序表分成由前55個(gè)數(shù)據(jù)元素組成的前半段和由后34個(gè)數(shù)據(jù)元素組成的后半段，那么前半段元素個(gè)數(shù)和整個(gè)有序表長(zhǎng)度的比值就接近黃金比值0.618，假如要查找的元素在前半段，那么繼續(xù)按照斐波那契數(shù)列來(lái)看，55 = 34 + 21，所以繼續(xù)把前半段分成前34個(gè)數(shù)據(jù)元素的前半段和后21個(gè)元素的后半段，繼續(xù)查找，如此反復(fù)，直到查找成功或失敗，這樣就把斐波那契數(shù)列應(yīng)用到查找算法中了。

package search;import java.util.Arrays;public class FibonagucciSearch {//因?yàn)楹竺嫖覀僲id=low+F(k-1)-1，需要使用到斐波那契數(shù)列，因此我們需要先獲取到一個(gè)斐波那契數(shù)列//非遞歸方法得到一個(gè)斐波那契數(shù)列public static int maxSize = 20;public static int[] fib() {int[] f = new int[maxSize];f[0] = 1;f[1] = 1;for (int i = 2; i < maxSize; i++) {f[i] = f[i - 1] + f[i - 2];}return f;}//編寫斐波那契查找算法//使用非遞歸方式編寫算法/*** @param a 數(shù)組* @param key key 我們需要查找的關(guān)鍵碼（值）* @return 返回對(duì)應(yīng)下標(biāo)，沒(méi)找到返回-1*/public static int fibonagucciSearch(int[] a, int key) {int low = 0;int high = a.length - 1;int k = 0; //表示斐波那契分割數(shù)值的下標(biāo)，找到k很重要int mid = 0; //存放mid值int[] f = fib();//獲取到斐波那契數(shù)列//獲取到斐波那契數(shù)列分割數(shù)值的下標(biāo)k//首先要明確：如果一個(gè)有序表的元素個(gè)數(shù)為n,并且n正好是（某個(gè)斐波那契數(shù) - 1），即n=F[k]-1時(shí)，才能用斐波那契查找法。 如果有序表的元素個(gè)n不等于（某個(gè)斐波那契數(shù) - 1），即n≠F[k]-1，這時(shí)必須要將有序表的元素?cái)U(kuò)展到大于n的那個(gè)斐波那契數(shù) - 1才行，這段代碼：while (high >= f[k] - 1) {//這里或者用 high+1 > f[k] - 1k++;}//因?yàn)閒[k] 值 可能大于a的長(zhǎng)度，因此我們需要使用Arrays類，構(gòu)造一個(gè)新的數(shù)組并指向temp[]//不足的部分會(huì)使用0填充int[] temp = Arrays.copyOf(a, f[k]);//實(shí)際上需要使用a數(shù)組的最后的數(shù)填充temp//舉例：//temp = {1,8,10,89,1000,1234,0,0} => {1,8,10,89,1000,1234,1234,1234}for (int i = high + 1; i < f[k] - 1; i++) {temp[i] = a[high];}//使用while循環(huán)來(lái)處理，找到我們的數(shù)keywhile (low <= high) { //只要這個(gè)條件滿足就可以找mid = low + f[k - 1] - 1;if (key < temp[mid]){ //我們應(yīng)該繼續(xù)向數(shù)組的前面查找（左邊）high = mid -1;//為什么是k--//1.全部元素 = 前面的元素 + 后邊的元素//2.f[k] = f[k-1]+f[k-2]//因?yàn)榍懊嬗衒[k-1]個(gè)元素，所以我們可以繼續(xù)拆分f[k-1] = f[k-2] + f[k-3]//即在f[k-1] 的前面繼續(xù)查找 k--//即下次循環(huán)mid = f[k-1-1]-1k--;}else if (key > temp[mid]){我們應(yīng)該繼續(xù)向數(shù)組的后面查找（右邊）low = mid +1;//為什么是k-2//說(shuō)明//1.全部元素 = 前面的元素 + 后邊的元素//2.f[k] = f[k-1]+f[k-2]//3.后面我們有f[k-2] 所以我們可以繼續(xù)拆分f[k-2] = f[k-3] + f[k-4]//4.即在f[k-2] 的前面進(jìn)行查找k-=2//5.即下次循環(huán)mid = f[k-1-2]-1k -= 2;}else {//找到//需要確定返回的是哪個(gè)下標(biāo)if (mid <= high){return mid;}else {return high;}}}return -1;}public static void main(String[] args) {int[] arr = {1, 8, 10, 89, 1000,1234};System.out.println(fibonagucciSearch(arr,10));} }

總結(jié)

以上是生活随笔為你收集整理的查找算法-（顺序查找、二分查找、插值查找、斐波那契查找）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。