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中基本的查詢演演算法。分別介紹了線性查詢演演算法，二分查詢演演算法，插值查詢演演算法，斐波那契查詢演演算法的基本思路以及使用程式碼進行了實現。
查詢演演算法有很多種，每一種都有各自的優缺點。在寫程式碼的過程中，首先腦子中得有這些基本演演算法的印象，遇到複雜的問題時，要學會選擇正確的演演算法，以便讓我們的程式碼效能更好。