1. 線性查找演算法

思路：

對陣列從左到右進行遍歷，依次把陣列的值與要查找的值進行對比，如果相等，就回傳此時的陣列下標，如果陣列遍歷完成之后，依然找不到該值，說明這個陣列中沒有此值，此時回傳-1，
線性查找是最簡單的查找演算法，但是查找的次數很多，

代碼

package Search;

public class SeqSearch {
    public static void main(String[] args) {
        int arr[] = {0, 29, 85, 66, 185, 18, 99};
        int res = seqSearch( arr, 10000 );
        if(res == -1){
            System.out.println("沒有找到該資料");
        }
        else{
            System.out.println(res);
        }
    }
    public static int seqSearch(int arr[], int value){
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == value){
                return i;
            }
        }
        return -1;
    }
}

2. 二分查找演算法

前提：陣列是一個有序的陣列，

思路：

代碼：

package Search;

public class BinerySearch {
    public static void main(String[] args) {
        int arr[] = {5, 20, 35, 88, 99, 180 };
        int res = binerySearch( arr, 0, arr.length - 1, 88 );
        System.out.println(res);
    }
    public static int binerySearch(int arr[], int left, int right, int value){
        int mid = (left + right) / 2;
        if(left > right){
            return -1;
        }else {
            if(arr[mid] > value){
                //向左進行遞回
                return binerySearch( arr, left, mid-1, value );
            }
            else if (arr[mid] < value){
                //向右進行遞回
                return binerySearch( arr, mid+1, right, value );
            }
            else {
                //說明找到了
                return mid;
            }
        }
    }
}

注意：上面只能找到陣列的一個下標，

下面的是怎么找到所有下標的代碼：

public static ArrayList<Integer> binerySearch2(int arr[], int left, int right, int value){
    //定義一個集合
    ArrayList<Integer> list = new ArrayList<>(  );
    int mid = (left + right) / 2;
    if(left > right){
        return list;
    }else {
        if(arr[mid] > value){
            //向左進行遞回
            return binerySearch2( arr, left, mid-1, value );
        }
        else if (arr[mid] < value){
            //向右進行遞回
            return binerySearch2( arr, mid+1, right, value );
        }
        else {
            list.add( mid );
            //找到之后不要回傳，向左掃描找到所有的值
            int temp = mid - 1;
            while(true){
                if(temp < 0 || arr[temp] != value){
                    break;
                }
                list.add(temp);
                temp--;
            }
            //找到之后不要回傳，向左遞回找到所有的值
            temp = mid + 1;
            while(true){
                if(temp > arr.length-1 || arr[temp] != value){
                    break;
                }
                list.add(temp);
                temp++;
            }
            return list;
        }
    }
}

3. 插值查找演算法

插值查找的原理：

插值查找演算法類似于二分查找，不同的是插值查找每次從自適應mid處開始查找，
將折半查找中的求mid 索引的公式 , low 表示左邊索引left, high表示右邊索引right.key 就是前面我們講的 value
int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;/插值索引/對應前面的代碼公式：int mid = left + (right – left) * (value– arr[left]) / (arr[right] – arr[left])

代碼：

package Search;

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 = insertSearch( arr, 0, arr.length - 1, 100 );
        System.out.println(res);
    }
    public static int insertSearch(int arr[], int left, int right, int value){
        if(left > right || value < arr[0] || value > arr[arr.length - 1]){
            return -1;
        }
        //利用公式求出mid
        int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);
        if(arr[mid] < value){
            //向右遞回
            return insertSearch( arr, mid + 1, right, value );
        }
        else if(arr[mid] > value){
            //向左遞回
            return insertSearch( arr, left, mid - 1, value );
        }
        else {
            //找到該值
            return mid;
        }
    }
}

4. 斐波那契查找演算法（黃金分割法）

思路：

黃金分割： 黃金分割是指將整體一分為二，較大部分與整體部分的比值等于較小部分與較大部分的比值，其比值約為0.618，這個比例被公認為是最能引起美感的比例，因此被稱為黃金分割，
斐波那契查找原理：利用斐波那契數列改變中間節點mid的位置，mid位于黃金分割點附近，
由斐波那契數列 F[k]=F[k-1]+F[k-2] 的性質，可以得到 （F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1 ，該式說明：只要順序表的長度為F[k]-1，則可以將該表分成長度為F[k-1]-1和F[k-2]-1的兩段，即如圖所示，從而中間位置為mid=low+F(k-1)-1
類似的，每一子段也可以用相同的方式分割
但順序表長度n不一定剛好等于F[k]-1，所以需要將原來的順序表長度n增加至F[k]-1，這里的k值只要能使得F[k]-1恰好大于或等于n即可，由以下代碼得到,順序表長度增加后，新增的位置（從n+1到F[k]-1位置），都賦為n位置的值即可

代碼：

package Search;

import java.util.Arrays;

public class fibonacciSearch {
    public static int maxSize = 20;
    public static void main(String[] args) {
        int arr[] = {1,9,11,90,1000,1500};
        System.out.println(fibSearch( arr,5646456 ));
    }
    //構建斐波那契數列
    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 arr  查找的陣列
     * @param key  要查找的值
     * @return 回傳對應下標，如果沒有回傳-1
     */
    public static int fibSearch(int arr[],int key){
        int low = 0;
        int high = arr.length - 1;
        int k = 0;  //表示斐波那契分割數值的下標
        int mid = 0;
        int f[] = fib(); //獲取斐波那契數列
        //獲取斐波那契分割數值得下標
        while(high > f[k] - 1 ){
            k ++;
        }
        //因為f[k]的值可能大于陣列的長度，所以重新構造一個陣列，并且指向arr
        int[] temp = Arrays.copyOf(arr, f[k]);
        //使用arr陣列的最后一個數填充temp
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }

        //使用while回圈查找的數key
        while(low <= high){
            //條件滿足一直找
            mid = low + f[k-1] - 1;
            if(key < temp[mid]){
                //向左邊查找
                high = mid - 1;
                k--;
            }else if(key > temp[mid]){
                //向右邊查找
                low = mid + 1;
                k = k - 2;
            }else {
                //找到
                //確定哪個是下標
                if(mid <= high){
                    return mid;
                }else{
                    return high;
                }
            }
        }
        return -1;
    }
}

總結

本文簡單的闡述了4中基本的查找演算法，分別介紹了線性查找演算法，二分查找演算法，插值查找演算法，斐波那契查找演算法的基本思路以及使用代碼進行了實作，
查找演算法有很多種，每一種都有各自的優缺點，在寫代碼的程序中，首先腦子中得有這些基本演算法的印象，遇到復雜的問題時，要學會選擇正確的演算法，以便讓我們的代碼性能更好，