這里寫自定義目錄標(biāo)題

• • 二分法
  • 插值查找算法
  • 斐波那契(黃金分割法)查找算法
  • 字符串暴力匹配算法
  • kmp字符串匹配算法

二分法

思想
每次和中間值進(jìn)行比較(以中間點(diǎn)為分割點(diǎn))
如果中間值小則取中間值右側(cè)部分中間值繼續(xù)比較
如果中間值大則取中間值左側(cè)部分中間值繼續(xù)比較
代碼

public class BinarySearchFind {public static void main(String[] args) {int [] arr = {1,8, 10, 89, 1000, 1234};int binarySearch = binarySearch(arr,0,arr.length-1,1234);System.out.println(arr[binarySearch]);}private static int binarySearch(int[] arr, int left, int right,int searchValue) {//代表數(shù)組中沒有這個(gè)值if(left>right){return -1;}//取得中間值int mid=(left+right)/2;if(searchValue<arr[mid]){//向左面進(jìn)行查找return binarySearch(arr,left,mid-1,searchValue);}else if(searchValue>arr[mid]){//向右面進(jìn)行查找return binarySearch(arr,mid+1,right,searchValue);}else{//返回位置return mid;}} }

插值查找算法

思想
和二分查找思想相同，
只是每次取的不是中間點(diǎn)(根據(jù)比例計(jì)算獲得分割點(diǎn))
如下圖:中間切割點(diǎn)如下

如下圖:經(jīng)過中間切割點(diǎn)思想 可以按比例獲得切割點(diǎn)位置

優(yōu)點(diǎn):對于數(shù)據(jù)量較大，關(guān)鍵字分布比較均勻的查找，采用插值查找, 速度比二分法快.
代碼

public class BinarySearchFind {public static void main(String[] args) {int [] arr = {1,8, 10, 89, 1000, 1234};int binarySearch = binarySearch(arr,0,arr.length-1,1234);System.out.println(arr[binarySearch]);}private static int binarySearch(int[] arr, int left, int right,int searchValue) {//代表數(shù)組中沒有這個(gè)值if(left>right){return -1;}//取得中間值int mid=left+(searchValue-arr[left])/(arr[right]-arr[left])*(right-left);if(searchValue<arr[mid]){//向左面進(jìn)行查找return binarySearch(arr,left,mid-1,searchValue);}else if(searchValue>arr[mid]){//向右面進(jìn)行查找return binarySearch(arr,mid+1,right,searchValue);}else{//返回位置return mid;}} }

斐波那契(黃金分割法)查找算法

思想
每次以0.618為分割點(diǎn)，在眾多數(shù)據(jù)中的得到的數(shù)據(jù)更加完美，但速度較慢
代碼

public class BinarySearchFind {public static void main(String[] args) {int [] arr = {1,8, 10, 89, 1000, 1234};System.out.println("index=" + fibSearch(arr, 1234));}private static int fibSearch(int[] arr, int searchValue) {//創(chuàng)建對應(yīng)的斐波那契數(shù)組int [] feiBoArr=new int[30];CreateFibonacciArray(feiBoArr);//找到數(shù)組長度對應(yīng)的斐波那契數(shù)中的值int k=0;while(feiBoArr[k]<arr.length){k++;}//將數(shù)組填充斐波那契長度,多出長度用0填充int[] tempArr=Arrays.copyOf(arr, feiBoArr[k]);//將最大數(shù)填充到數(shù)組末尾 [1, 8, 10, 89, 1000, 1234, 1234, 1234]for(int i=arr.length;i<tempArr.length;i++){tempArr[i]=arr[arr.length-1];}int left=0;int right=tempArr.length-1;while(left<right){//中間坐標(biāo)位置 =左面坐標(biāo)+斐波納契中間坐標(biāo)int mid=left+feiBoArr[k-1];if(searchValue >tempArr[mid]){//要查找的值在右面left=mid+1;//1. 全部元素 = 前面的元素 + 后邊元素//2. f[x]=f[x-2]+f[x-1]//其中f[x-2] 為左面部分,f[x-1]為右面部分//f[x-2]<f[x-1], 右面部分大//下次的分割點(diǎn)就是 f[x-1-1]k--;}else if(searchValue < tempArr[mid]){//要查找的值在左面right=mid-1;//1. 全部元素 = 前面的元素 + 后邊元素//2. f[x]=f[x-2]+f[x-1]//其中f[x-2] 為左面部分,f[x-1]為右面部分//f[x-2]<f[x-1], 左面部分小 //下次的分割點(diǎn)就是 f[x-2-1]k--;k--;}else{//因?yàn)楹竺嬗械臄?shù)是填充的,如果匹配到填充的數(shù),則直接返回?cái)?shù)組最大索引if(arr[arr.length-1]==tempArr[mid]){return arr.length-1;}return mid;}}return -1;}/*** 創(chuàng)建斐波那契數(shù)組*/public static void CreateFibonacciArray(int[] arr){arr[0]=1;arr[1]=1;for(int i=2;i<arr.length;i++){arr[i]=arr[i-1]+arr[i-2]; }}}

字符串暴力匹配算法

思想
每次只移動一位，若是不匹配，移動到下一位接著判斷，浪費(fèi)了大量的時(shí)間
代碼

public class ViolenceMatch {public static void main(String[] args) {String str="asdfa asdfb asdfc asdfd";String match="asdfc";int index=violenceMatch(str,match);System.out.println(index);}private static int violenceMatch(String str, String match) {//每次匹配失敗復(fù)原的位置int temp=0;//循環(huán)遍歷每個(gè)字符for(int i=0,j=0;i<str.length();i++){temp=i;while(str.charAt(i) == match.charAt(j)){i++;j++;if(j == match.length()){//返回匹配出來的位置return i-match.length();}}//這里應(yīng)用回溯i=temp;j=0;}return -1;} }

kmp字符串匹配算法

思想
在匹配不成功時(shí)回溯的位置不是下一位，而是經(jīng)過計(jì)算的指定位置
圖解
部分匹配值”就是”前綴”和”后綴”的最長的共有元素的長度。以”ABCDABD”為例
－”A”的前綴和后綴都為空集，共有元素的長度為0；
－”AB”的前綴為[A]，后綴為[B]，共有元素的長度為0；
－”ABC”的前綴為[A, AB]，后綴為[BC, C]，共有元素的長度0；
－”ABCD”的前綴為[A, AB, ABC]，后綴為[BCD, CD, D]，共有元素的長度為0；
－”ABCDA”的前綴為[A, AB, ABC, ABCD]，后綴為[BCDA, CDA, DA, A]，共有元素為”A”，A的長度為1；
－”ABCDAB”的前綴為[A, AB, ABC, ABCD, ABCDA]，后綴為[BCDAB, CDAB, DAB, AB, B]，共有元素為”AB”，AB的長度為2；
－”ABCDABD”的前綴為[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后綴為[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的長度為0。

代碼

總結(jié)

以上是生活随笔為你收集整理的查找算法-志宇的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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