常用查找算法：

1. 线性查找
2. 二分查找
3. 插值查找
4. 斐波那契查找

线性查找

直接遍历查找

for(int i = 0; i < arr.length; i++){
    //遍历
}

二分查找

对于有序的目标集进行查找。

查找一个有序数组中是否存在target 存在返回索引 否则返回-1

/**
     * 查找元素，存在返回索引，不存在返回-1
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearch(int[] arr, int target) {
        int left = 0,right = arr.length-1; //注意
        while (left <= right) { //注意
            //这样写是为了防止溢出
            int mid = right - (right - left)/2;
            if (arr[mid] > target) {
                right = mid-1;
            }else if(arr[mid] < target) {
                left = mid +1;
            }else {
                return mid;
            }
        }
        return -1;
    }

查找一个有序数组中是否存在target 存在返回最左侧索引 否则返回-1

/**
     * 查找元素，存在返回最左侧的索引，不存在返回-1
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearch(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int left = 0;
        int right = nums.length; // 注意
        while (left < right) { // 注意
            int mid = (left + right)/2; 
            //这两个值不一定相同。
            System.out.println((right + (left - right)/2) == ((left + right)/2));
            if (nums[mid] == target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid; // 注意
            }
        }
        // target 比所有数都大
        if (left == nums.length) return -1;
        // 类似之前算法的处理方式
        return nums[left] == target ? left : -1;
    }

查找一个有序数组中是否存在target 存在返回最右侧索引 否则返回-1

/**
     * 查找元素，存在返回最右侧的索引，不存在返回-1
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearch(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int left = 0;
        int right = nums.length; // 注意
        while (left < right) { // 注意
            int mid = (left + right)/2; 
            //这两个值不一定相同。
            System.out.println((right + (left - right)/2) == ((left + right)/2));
            if (nums[mid] == target) {
                left = mid+1; //注意
            } else if (nums[mid] < target) {
                 left = mid + 1;
            } else if (nums[mid] > target) {
                 right = mid; // 注意
            }
        }
        if (left == 0) return -1;
        return nums[left-1] == target ? (left-1) : -1;
    }

插值查找

插值查找算法类似于二分查找，不同的是插值每次从自适应mid出开始查找。

int mid = left + (right - left) * (target - arr[left]) / (arr[right] - arr[left]);

要求也是数据集是有序的。

public static int insertVal(int[] arr,int target){
    if (arr.length == 0){
            return -1;
        }
        if (target < arr[0] || target > arr[arr.length - 1]){
            return - 1;
        }
        int left = 0,right = arr.length - 1;
        while (left < right){
            int mid = left + (right - left) * (target - arr[left]) / (arr[right] - arr[left]);
            if (arr[mid] > target){
                right = mid - 1;
            }else if (arr[mid] < target){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return arr[left] == target ? left : -1;
    }

注意事项：

对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快。

关键字分布不均匀的情况下，该方法不一定比二分查找好。

斐波那契（黄金分割）查找

黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这一部分的之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称中外比。

斐波那契数列两个相邻的数之间的比值，无限接近黄金分割值。

原理：斐波那契查找原理与前两种类似，仅仅改变了中间节点mid的位置，mid不再是中间或者插值得到，而是位于黄金分割点附近，即：

int mid = low+ F(k-1) - 1 （F代表斐波那契数列） 如下图：

对F(k-1) - 1的理解

由斐波那契数列 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位置的值即可。

while(n>fib(k)-1)

k++;

代码：

public static int fibSearch(int[] arr, int target){
        //k表示 斐波那契数列的下标
        int left = 0, right = arr.length - 1, k = 0,mid;
        int[] f = fib(arr.length);
        //获取斐波那契数列 分割数值得下标
        while (right > f[k] - 1){
            k ++;
        }
        //因为 f[k] 的值可能会大于 arr的长度 因此重新构造，不足部分补充arr[right]
        int[] temp = Arrays.copyOf(arr, f[k]);
        for (int i = right + 1; i < temp.length; i++) {
            temp[i] = arr[right];
        }
        while (left <= right){
            mid = left + f[k-1] - 1;
            if (target < temp[mid]){
                right = mid - 1;
                // 说明为什么k-1 此时说明应该继续向左寻找
                // 全部元素 = 前面元素 + 后面元素
                // 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 (target > temp[mid]){
                left = mid + 1;
                // 说明为什么k-2 此时说明应该继续向右寻找
                // 全部元素 = 前面元素 + 后面元素
                // f[k] = f[k-1] + f[k-2]
                // 因为后面有 f[k-2] 有个元素，所以可以继续拆分 f[k-2] = f[k-3] + f[k-4]
                // 即在 f[k-2] 的前面继续查找k-=2 即下次循环 mid = f[k-1-2] - 1
                k -= 2;
            }else{
                return Math.min(mid, right);
            }
        }
        return -1;
    }

以斐波那契数列为辅助，寻找数组中黄金分割点的索引位置。