一、順序查找（線性查找）
順序查找太簡單了，沒什麼好說的，直接循環找到等于的就傳回，沒有找到就傳回-1
代碼實作
//順序查找(線性查找)
public class SeqSearch {
public static void main(String[] args) {
int arr[] = {1,9,11,-1,34,89}; //沒有順序的數組
int index = seqSearch(arr,11);
if (index == -1){
System.out.println("沒有找到");
}else{
System.out.println("找到了，下标為："+index);
}
}
public static int seqSearch(int[] arr,int value){
//線性查找是逐一比對，發現有相同值，就傳回下标
for (int i=0;i<arr.length;i++){
if (arr[i]==value){
return i;
}
}
return -1;
}
}
二、二分查找（折半查找）
使用二分查找的前提是 這個數組是有序的
思路分析
1、首先确定改數組的中間的下标 mid = (left+right)/2
2、然後讓需要查找的數findVal和arr[mid]比較
- 如果findVal>arr[mid]，說明你要查找的數在mid右邊，遞歸向右查詢
- 如果findVal<arr[mid]，說明你要查找的數在mid左邊，遞歸向左查詢
- 如果findVal==arr[mid]，說明找到了直接傳回
3、找到就結束遞歸
4、遞歸完還沒找到也結束遞歸
代碼實作 (遞歸）
public class BinarySearch {
public static void main(String[] args) {
int arr[] = {1,8,10,89,1000};
int resIndex = binarySearch(arr,0, arr.length-1,88 );
if (resIndex!=-1){
System.out.println("要找的值索引為："+resIndex);
}else {
System.out.println("數組沒有這個數");
}
}
//二分查找算法
public static int binarySearch(int[] arr,int left,int right,int findVal){
//當left>right說明遞歸完整個數組了還是沒有找到
if (left>right){
return -1;
}
int mid = (left+right)/2;
int midVal = arr[mid];
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 class BinarySearch {
public static void main(String[] args) {
int arr[] = {1,8,10,89,1000,1000,1000};
ArrayList resIndexList = binarySearch(arr,0, arr.length-1,1000 );
System.out.println(resIndexList);
}
//二分查找算法
public static ArrayList<Integer> binarySearch(int[] arr,int left,int right,int findVal){
//當left>right說明遞歸完整個數組了還是沒有找到
if (left>right){
return new ArrayList<>();
}
int mid = (left+right)/2;
int midVal = arr[mid];
if (findVal>midVal){ //向右遞歸
return binarySearch(arr,mid+1,right,findVal);
}else if (findVal<midVal){
return binarySearch(arr,left,mid-1,findVal);
}else{
ArrayList<Integer> resIndexlist = new ArrayList<>();
int temp = mid-1;
while(true){
if (temp <0 || arr[temp]!=findVal){
break;
}
//否則放入集合中
resIndexlist.add(temp);
temp-=1; //左移
}
resIndexlist.add(mid);
temp = mid+1;
while(true){
if (temp > arr.length-1 || arr[temp]!=findVal){
break;
}
//否則放入集合中
resIndexlist.add(temp);
temp+=1; //左移
}
resIndexlist.add(mid);
return resIndexlist;
}
}
}
代碼實作（非遞歸）
public class BinarySearchNoRecur {
public static void main(String[] args) {
int[] arr = {1,3,8,10,11,67,100};
int index=binarySearch(arr,11);
System.out.println(index);
}
/**
*
* @param arr 待查找的數組
* @param target 需要查找的數
* @return 傳回對應的下标，-1表示沒有找到
*/
public static int binarySearch(int[] arr,int target){
int left = 0;
int right = arr.length-1;
while(left<=right){ //說明繼續找
int mid = (left+right)/2;
if (arr[mid]==target){
return mid;
}else if (arr[mid]>target){
right = mid-1; //需要向左邊查找
}else {
left = mid+1;
}
}
return -1;
}
}
三、插值查找算法
插值查找算法類似于二分查找，不同的是插值查找每次從自适應mid處開始查找
是對二分查找算法進行的優化，如果每次折半其實效率并不高，是以我們對mid的公式進行優化
int mid = left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left])
他是一種自适應的寫法 因為他本身的值也參加了mid的運算
代碼實作
public class InsertValueSearch {
public static void main(String[] args) {
int arr[] = new int[100];
for (int i=0;i<100;i++){
arr[i]=i+1;
}
int res = insertValueSearch(arr,0, arr.length-1, 99);
System.out.println(res);
}
//插值查找也要求數組有序
public static int insertValueSearch(int[] arr,int left,int right,int findVal){
//findVal<arr[0] || findVal>arr[arr.length-1]是必須要加的 否則可能越界
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 insertValueSearch(arr, left, mid-1, findVal);
} else if (findVal>midVal) {
return insertValueSearch(arr, mid+1, right, findVal);
} else {
return mid;
}
}
}
注意事項
對于資料量較大，關鍵字分布比較均勻的查找來說，采用插值查找，速度比較快。
關鍵詞分布不均勻的情況下，改方法不一定比折半快
四、斐波那契查找（黃金分割法）
斐波那契數列{1,1,2,3,5,8,13,21,34,55}
發現斐波那契數列相鄰兩個數的比例，無限接近黃金分割值0.618
原理分析
原理與前面兩種相似，僅僅改變了中間點mid的位置，mid不再是中間或者插值得到，而是位于黃金分割點附近
根據對斐波那契數列 F[k] = F[K-1] + F[K-2] 可得 (F[k]-1)=(F[k-1]-1)+(F[k-1]-1)
說明：隻要順序表長度為F[k]-1 就可以分為(F[k-1]-1)和(F[k-1]-1)兩段，如圖
是以中間值 mid = low + F[K-1]- 1
注意：我們的順序表不一定等于F[k]-1 是以我們需要把他從n擴充到F[K]-1 （這裡的k值隻要能使得F[k]-1恰好大于或等于n即可，由以下代碼得到,順序表長度增加後，新增的位置（從n+1到F[k]-1位置），都賦為n位置的值即可。）
while(n>fib(k)-1)
k++;
代碼實作
public class FibonacciSearch {
public static int maxSize = 20;
public static void main(String[] args) {
int [] arr = {1,8,10,89,1000,1234};
System.out.println("index = "+fibSearch(arr,1));
}
//因為後面我們mid=low+f(k-1)-1 需要斐波那契數列 是以我們需要得到一個斐波那契數組
//非遞歸得斐波那契數列（效率高些）
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;
}
//編寫斐波那契查找算法
public static int fibSearch(int[] a,int key){
int low = 0;
int high = a.length-1;
int k = 0; //斐波那契分割數值的下标
int mid = 0;
int f[] = fib();//擷取斐波那契數列
//擷取斐波那契分割數列的下标
while (high>f[k]-1){
k++;
}
//因為f[k]值可能大于a的長度，是以我們需要使用Array構造新的數組并指向a[]
int[] temp = Arrays.copyOf(a,f[k]); //不足的部分用0填充
//實際用a數組的最後一個數來填充數組
for (int i = high +1;i< temp.length;i++){
temp[i] = a[high];
}
//使用while循環處理，得到我們的數key
while(low<=high){
mid = low+f[k-1]-1;
if (key<temp[mid]){ //說明向左找
high = mid -1 ;
//1、全部的元素=前面的元素+後面的元素
//2、f[k] = f[k-1]+f[k-2]
//因為前面有f[k-1]個元素，是以可以繼續拆分 f[k-1] = f[k-2]+f[k-3]
//即在f[k-1]的前面繼續查找，k--
//即下次循環的時候 mid = f[k-1-1]-1
k --;
}else if (key> temp[mid]){
high = mid+1;
//1、全部的元素=前面的元素+後面的元素
//2、f[k] = f[k-1]+f[k-2]
//3、因為後面有f[k-2]，是以可以繼續拆分 f[k-1] = f[k-3] +f[k-4]
//4、即在f[k-2]的前面進行查找 k-=2
//即下次循環的時候 mid = f[k-1-2]-1
k-=2;
}else { //找到
if(mid<=high){
return mid;
}else{
return high;//因為填充了 high可能找的就是那個high
}
}
}
return -1;
}
}
分析難點
第一個if判斷是向數組左邊開始查找，那麼對于左邊的資料，相比全部資料而言，它的長度是f[k-1]-1,之後f[k-1]-1又作為一個整體來查找，即k要自減1。對于右側的資料，它的長度為f[k-2]-1，之後，它也會作為一個整體來查找，是以k要減2。
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)