🍅 作者主頁(yè)：Roninaxious
🍅 歡迎點(diǎn)贊 👍 收藏 ?留言 📝
🍅 話不多說 🍁開卷！

• 🚢 順序查找算法
• 🚢 二分查找算法
• • 💥優(yōu)化二分查找算法
• 🚢 插值查找算法
• 🚢 斐波那契查找算法
• • 💥優(yōu)化斐波那契查找算法

---

🚢 順序查找算法

🙄對(duì)于順序查找算法比較容易理解，遍歷一個(gè)數(shù)組即可，如果找到該值返回對(duì)應(yīng)的下標(biāo)即可.🙄

🧧源代碼🧧

/*** 如果返回的是-1，則數(shù)組中無相關(guān)值* @param arr 待搜索數(shù)組* @param value 待搜索值* @return -1或者 索引值*/private static int seqSearch(int[] arr, int value) {for (int i = 0; i < arr.length; i++) {if (arr[i] == value) { //如果找到對(duì)應(yīng)的值return i; //返回對(duì)應(yīng)的索引}}return -1; //沒有找到返回-1}

🎐測(cè)試代碼🎐

public static void main(String[] args) {int[] arr = {1, 34, -1, 5, 8, 2, 99};int index = seqSearch(arr, 8);if (index == -1) {System.out.println("無相關(guān)值!");} else {System.out.println("改值對(duì)應(yīng)的索引下標(biāo)為:"+index);}}

---

🚢 二分查找算法

🙄對(duì)于某一個(gè)數(shù)組arr(這個(gè)數(shù)組是有序的,假設(shè)是升序)，我們想要從數(shù)組中找到值value，返回它對(duì)應(yīng)得索引
begin = 0;
end = arr.length
mid = (begin+end)/2
這三個(gè)變量begin、mid、end對(duì)應(yīng)這數(shù)組的下表
1.我們將value與arr[mid]進(jìn)行比較
2.如果value > arr[mid]，那么我們只需要在mid的右邊進(jìn)行搜索即可；如果value < arr[mid]，我們只需要在mid的左邊進(jìn)行搜索即可.
🙄
🎐注意點(diǎn)🎐
Ⅰ.如果數(shù)組不是有序的，則需要將其進(jìn)行排序后再操作
Ⅱ.使用遞歸能夠很好實(shí)現(xiàn)

二分查找需要一定的遞歸知識(shí)

【??_{爆肝萬字總結(jié)遞歸}??玩轉(zhuǎn)算法系列之我如何才能掌握遞歸解題的能力??_{十大經(jīng)典問題助你突破極限}??】:https://blog.csdn.net/Kevinnsm/article/details/120445071?spm=1001.2014.3001.5501

🧧源代碼🧧

/***二分查找算法* @param arr 待搜索的數(shù)組* @param value 待查找的值* @param begin 左邊的索引* @param end 右邊的索引* @return 如果找到該值，就返回其對(duì)應(yīng)的下標(biāo)，否者返回其-1*/private static int binarySearch(int[] arr, int value, int begin, int end) {if (begin > end) {return -1;}int mid = (begin + end) / 2; //取中間值if (value > arr[mid]) {return binarySearch(arr, value, mid + 1, end);} else if (value < arr[mid]) {return binarySearch(arr, value, begin, mid - 1);} else {return mid;}}

🎐測(cè)試代碼🎐

public static void main(String[] args) {int[] arr = {1,3, 4, 5, 8, 11, 23, 77};int index = binarySearch(arr, 8, 0, arr.length - 1);if (index == -1) {System.out.println("未找到該值!");} else {System.out.println(index);}}

💥優(yōu)化二分查找算法

??如果一個(gè)數(shù)組是[1,2,4,5,6,8,8,8,8,11,23]，一旦查找其他的8，那么如果使用上面的查找算法，就只能返回一個(gè)索引值；因此，對(duì)該查找算法進(jìn)行優(yōu)化，讓其能夠返回所有的索引值??

/*** 默認(rèn)是升序數(shù)組* 對(duì)上部分進(jìn)行優(yōu)化，能夠查出重復(fù)數(shù)據(jù)的所有下表* @param arr 待搜索數(shù)組* @param value 待查詢的值* @param begin 左索引* @param end 右索引* @param list 存儲(chǔ)搜索值下表的集合*/private static void binarySearch2(int[] arr, int value, int begin, int end, List<Integer> list) {if (begin > end) { //遞歸結(jié)束條件return;}int mid = (begin + end) / 2; //取中值if (value > arr[mid]) { //說明需要去mid右邊查找binarySearch2(arr, value, mid + 1, end, list); //遞歸進(jìn)入 mid+1 至 end這一段數(shù)據(jù)} else if (value < arr[mid]) { //說明需要去mid左邊查找binarySearch2(arr, value, begin, mid - 1, list); //遞歸進(jìn)入 begin 至 mid-1這一段數(shù)據(jù)} else if (value == arr[mid]) { //說明找到了待查找的值；此時(shí)需要考慮的是在這個(gè)值的左邊和右邊可能有相同的數(shù)據(jù)int tempFront = mid - 1; //例如arr [1,8,8,8,9],找到arr[2],它的前后都有8，所以需要進(jìn)行判斷while (true) { //這個(gè)while循環(huán)是對(duì)arr[2]左邊進(jìn)行判斷是否有8if (tempFront < 0 || value != arr[tempFront]) { //這當(dāng)上面的mid為0時(shí)，這個(gè)tempFront為-1，所以需要進(jìn)行判斷break; //又或者左邊第一個(gè)就不等于value，那么直接break即可}list.add(tempFront); //將符合value=8的索引值加入到list集合中tempFront--;}list.add(mid); //將arr[2]加入到集合中，至于為什么現(xiàn)在加入是因?yàn)榘凑諒拇蟮叫?list[2,3,4]int tempAfter = mid + 1;while (true) { //右邊類似于左邊if (tempAfter > end || value != arr[tempAfter]) {break;}list.add(tempAfter);tempAfter++;}}}

🎐測(cè)試代碼🎐

public static void main(String[] args) {int[] arr = {1,3, 4, 5, 5, 5, 5, 11, 23, 77};List<Integer> list = new ArrayList<>();binarySearch2(arr, 5, 0, arr.length - 1, list);if (list.isEmpty()) {System.out.println("未找到該值!");} else {System.out.println(list.toString());}}

🥫分析以上的二分查找算法

根據(jù)它的 int mid = (begin+end)/2 ，我們可以推算二分算法適用于什么場(chǎng)景；
假設(shè)一個(gè)數(shù)組為arr[1,2,3,4,5…,98,99,100] ，我們要找尋1這個(gè)值，那么需要幾次找到呢？看下面的運(yùn)行結(jié)果

可以看出經(jīng)歷了六次循環(huán)調(diào)用才找到；如果我們找value=50,那么一次就能成功！所以這個(gè)調(diào)用多少次與mid的取值也有很大關(guān)系；

分析mid=(begin+end)/2，看出begin、end無法做出改變，那么只有對(duì)1/2進(jìn)行改動(dòng)；mid=begin + (begin+end) / {(value-arr[begin])/(arr[end]-arr[begin])}，根據(jù)上文中找尋1，我們可以算出mid = 1，所以一步就能找到；這就是下文提到的插值查找

---

🚢 插值查找算法

根據(jù)上文進(jìn)行分析，這個(gè)插值查找算法是對(duì)二分查找算法的改進(jìn)。
mid=(begin+end) / {(value-arr[begin]) / (arr[end]-arr[begin])}

?下面這段源代碼除了mid求的不一樣之外，其他一模一樣。?

/*** 自適應(yīng)求出mid* @param arr 待搜索數(shù)組* @param value 待查詢的值* @param begin 左索引* @param end 右索引* @param list 存儲(chǔ)搜索值下表的集合*/private static void interpolationSearch(int[] arr, int value, int begin, int end, List<Integer> list) {System.out.println("test");//這個(gè)value要進(jìn)行判斷是否小于arr[0]，否者在下面求mid時(shí)會(huì)報(bào)錯(cuò)if (begin > value || value < arr[0] || value > arr.length - 1) {return;}int mid = begin + (begin + end) * (value - arr[begin]) / (arr[end] - arr[begin]);if (value > arr[mid]) {interpolationSearch(arr, value, mid + 1, end, list);} else if (value < arr[mid]) {interpolationSearch(arr, value, begin, mid - 1, list);} else if (value == arr[mid]) {int tempFront = mid - 1;while (true) {if (tempFront < 0 || value != arr[tempFront]) {break;}list.add(tempFront);tempFront--;}list.add(mid);int tempAfter = mid + 1;while (true) {if (tempAfter > end || value != arr[tempAfter]) {break;}list.add(tempAfter);tempAfter++;}}}

根據(jù)數(shù)組為arr[1,2,3,4,5…,98,99,100] ，查找其中的1，只需一次便能查到.

---

🚢 斐波那契查找算法

🎐這個(gè)斐波那契(黃金分割法)是對(duì)二分法的改進(jìn)，也就是和插值查找類似；通過改變mid的取值方式來達(dá)到，每次都在黃金分割點(diǎn)附近。

這個(gè)斐波那契查找需要借助斐波那契數(shù)列來實(shí)現(xiàn)

public class FibonacciSearch {private static final int MAX_SIZE = 10;public static void main(String[] args) {int[] arr = {1, 3, 5, 8, 9, 12, 33, 44};int index = fibonacciSearch(arr, 44);if (index == -1) {System.out.println("未找到該值!");} else {System.out.println(index);}}/*** 默認(rèn)是升序序列* 流程：* 1.構(gòu)建斐波那契數(shù)列* 2.定k值,也就是根據(jù)f(k)-1 = f(k-1)- 1 + f(k-2)-1 +1;必須將待搜索的數(shù)組擴(kuò)容至f(k) - 1* 3.將擴(kuò)容部分的數(shù)據(jù)賦值原數(shù)組的arr[end]* 4.while循環(huán)判斷** @param arr 待搜索數(shù)組* @param value 待查詢的值* @return 如果未搜索到相關(guān)的值,返回-1，如果搜索到了就返回對(duì)應(yīng)的索引*/private static int fibonacciSearch(int[] arr, int value) {int begin = 0;int end = arr.length;int k = 0;int[] f = fib(); //構(gòu)建一個(gè)斐波那契數(shù)列,斐波那契查找需要借助斐波那契數(shù)列來完成while (end > f[k] - 1) { //每次都將k進(jìn)行++,直到f[k]-1大于或等于數(shù)組長(zhǎng)度（斐波那契數(shù)列是1，1，2，3，5，8...）那么f[k] - 1有可能稍微大于數(shù)組長(zhǎng)度++k; //至于為什么要將數(shù)組大小定到f[k] - 1 --》 f[k]=f[k-1]+f[k-2] --> f[k]-1 = f[k-1]-1 + f[k-2]-1 +1} //剛好將數(shù)組分為三部分 即f[k-1]-1 、f[k-2]-1、1(1也就是mid)int[] temp = Arrays.copyOf(arr, f[k] - 1); //由于f[k-1]可能大于數(shù)組長(zhǎng)度，所以要進(jìn)行擴(kuò)容處理for (int j = end + 1; j < f[k] - 1; j++) {temp[j] = temp[end]; //將擴(kuò)容部分的數(shù)據(jù)定義為原數(shù)組最后一個(gè)數(shù)據(jù)(也就是最大值)}while (begin < end) { //跳出條件，int mid = begin + f[k - 1] - 1; //斐波那契數(shù)列的mid求解方式if (value < temp[mid]) { //說明在mid的左邊，左邊是f[k-1]-1部分k--; //k-- 代表 f[k-1]-1,左邊部分剛好f[k-1]-1 = f[k-2]-1 + f[k-3]-1end = mid - 1;} else if (value > temp[mid]) {k = k - 2; // k=k-2代表f[k-2]-1，這是因?yàn)樵谟疫協(xié)[k-2]-1部分；f[k-2]-1 = f[k-3]-1 + f[k-4]-1begin = mid + 1;} else {if (mid > arr.length) { //判斷mid是否在擴(kuò)容部分return end;} else {return mid;}}}return -1;}/*** 創(chuàng)建一個(gè)斐波那契數(shù)列,供黃金分割法查找時(shí)使用* @return 斐波那契數(shù)列數(shù)組*/private static int[] fib() {int[] f = new int[MAX_SIZE];f[0] = 1;f[1] = 1;for (int i = 2; i < f.length; i++) {f[i] = f[i - 1] + f[i - 2];}return f;}

💥優(yōu)化斐波那契查找算法

對(duì)于上面的斐波那契查找算法，我們可以看出對(duì)找尋重復(fù)的數(shù)組元素是不行的(例如[1,2,8,8,8,8,9],找尋其中的8,只能返回一個(gè)索引]；所以對(duì)其進(jìn)行改進(jìn)，將索引加入到集合當(dāng)中。

思路基本上和上文一樣.

package com.zsh.algorithm.search;import java.util.ArrayList; import java.util.Arrays; import java.util.List;/*** @author:Ronin* @since:2021/9/25* @email:1817937322@qq.com*/ public class FibonacciSearchImprove {private static final Integer MAX_SIZE = 10;public static void main(String[] args) {int[] arr = {1, 3, 5, 6, 8, 10, 22, 22, 22};List<Integer> list = new ArrayList<>();fibonacciSearch(arr, list, 22);if (list.isEmpty()) {System.out.println("未找到該值!");} else {System.out.println(list.toString());}}/*** 對(duì)斐波那契查找進(jìn)行改進(jìn)，支持重復(fù)元素** @param arr 待搜索集合* @param list 下標(biāo)集合* @param value 待查詢的值*/private static void fibonacciSearch(int[] arr, List<Integer> list, int value) {int[] f = fib();int k = 0;int begin = 0;int end = arr.length - 1;int n = arr.length;int mid = 0;while (n > f[k] - 1) {++k;}int[] temp = Arrays.copyOf(arr, f[k] - 1);for (int j = end + 1; j < f[k] - 1; j++) {temp[j] = temp[end];}while (begin < end) {mid = begin + f[k - 1] - 1;if (value < temp[mid]) {k--;end = mid - 1;} else if (value > temp[mid]) {k -= 2;begin = mid + 1;} else {int tempFront = mid - 1;while (tempFront >= 0) {if (value == temp[tempFront]) {list.add(tempFront);tempFront--;} else {break;}}list.add(mid);int tempAfter = mid + 1;while (tempAfter <= end) {if (value == temp[tempAfter]) {list.add(tempAfter);tempAfter++;} else {break;}}break;}}}//創(chuàng)建一個(gè)斐波那契數(shù)列private static int[] fib() {int[] f = new int[MAX_SIZE];f[0] = 1;f[1] = 1;for (int i = 2; i < f.length; i++) {f[i] = f[i - 1] + f[i - 2];}return f;} }

總結(jié)

以上是生活随笔為你收集整理的【算法系列之万字总结常用的查找算法，持续补充更新中】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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