查找算法

• 顺序（线性）查找
• 二分查找/折半查找
• 插值查找

• 斐波拉契查找

  1. 线性查找算法

  1.1 思想

• 遍历所有元素，一个接着一个判断，直到找到目标值为止

  1.2 实现

  public class SeqSearch {
    public int seqSearch(int[] arr,int target){
        for (int i=0;i<arr.length;i++){
            if (arr[i]==target) return i;
        }
        return -1;
    }
  }

  2. 二分查找

  2.1 思路

• 前提是一个有序数组

• 通过找到中间值，然后进行判断
  • 等于，直接返回下标
  • 大于，向中间值的右边进行递归
  • 小于，向中间值的左边进行递归

• 注意， 递归的停止条件：

  • 当传入的左边界值大于右边界值那就直接返回-1，表示未找到

    2.2 实现

    ```java public class BinarySearch { public int binarySearch(int[] arr,int left,int right,int target){ // 递归停止条件,表示没有找到 if (left>right) return -1;

    int mid = (left+right)/2; int midVal = arr[mid];

    if (target==midVal){

       return mid;

    } if (target<midVal){

       return binarySearch(arr,left,mid-1,target);
    

    }else {

       return binarySearch(arr,mid+1,right,target);
    

    } } }

<a name="4dqfM"></a>
### 2.3 改造二分法

- 通过改造二分法，使得二分查找能够返回数组中等于目标值的所有下标

- 思路
   - 当找到目标值时，进行左右循环判断，只要左右两边有值与目标值相等，那么就记录下这个坐标
   - 循环查找两边，直到找到不与目标值相等的元素停止

- 实现
```java
    //  能够返回目标值的所有坐标的二分查找
    public List<Integer> binarySearchPlus(int[] arr,int left,int right,int target){
        if (left>right) return new ArrayList<Integer>();
        int mid = (left+right)/2;
        int midVal = arr[mid];
        if (target==midVal){
            List<Integer> res = new ArrayList<>();
            int l = mid - 1;
            while(l>=0 && target==arr[l]){
                res.add(l);
                l--;
            }
            res.add(mid);
            int r = mid+1;
            while(r<arr.length && target==arr[r]){
                res.add(r);
                r++;
            }
            return res;
        }
        if (target<midVal){
            return binarySearchPlus(arr,left,mid-1,target);
        }else {
            return binarySearchPlus(arr,mid+1,right,target);
        }
    }

3. 插值查找

3.1 介绍

• 类似于二分查找，可视作二分查找的升级。

• 相比于二分查找：

  • 二分查找简单的定位到数组的中心，然后根据目标值来判断向左还是向右递归
  • 插值查找每次的定位方式不同，会更加准确的定位到目标值的位置

    3.2 思想

• 定位方式：

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

    3.3 实现

    public class InsertValueSearch {
    // 返回单个元素的下标
    public int insertValueSearch(int[] arr,int left,int right,int target){
       int mid = left+(right-left)*(target-arr[left])/(arr[right]-arr[left]);
       int midVal = arr[mid];
       if (target==midVal){
           return mid;
       }else if (target<midVal){
           return insertValueSearch(arr,left,mid-1,target);
       }else {
           return insertValueSearch(arr,mid+1,right,target);
       }
    }
    // 返回所有满足条件的元素的下标
    public List<Integer> insertValueSearchPlus(int[] arr,int left,int right,int target){
       int mid = left+(right-left)*(target-left)/(arr[right]-arr[left]);
       int midVal = arr[mid];
       if (target==midVal){
           List<Integer> res = new ArrayList<>();
           int l = mid-1;
           int r = mid+1;
           while(l>=0 && arr[l]==target){
               res.add(l);
               l--;
           }
           res.add(mid);
           while(r<arr.length && target==arr[r]){
               res.add(r);
               r++;
           }
           return res;
       }else if (target<midVal){
           return insertValueSearchPlus(arr,left,mid-1,target);
       }else {
           return insertValueSearchPlus(arr,mid+1,right,target);
       }
    
    }
    }
    

    4. 斐波拉契查找(黄金分割)

    4.1 原理

    4.2 实现

    public class FibonacciSearch {
    // 获取斐波拉契数列
    public int[] fib(int maxSize){
       int[] f = new int[maxSize];
       f[0] = 1;
       f[1] = 1;
       for (int i=2;i<f.length;i++){
           f[i] = f[i-1] + f[i-2];
       }
       return f;
    }
    
    public int fibSearch(int[] arr,int target){
       int low = 0;
       int high = arr.length-1;
       int k = 0;
       int mid = 0;
       int f[] = fib(20);
       while(high>f[k]-1){
           k++;
       }
       int[] temp = Arrays.copyOf(arr,f[k]);
       for (int i=high+1;i<temp.length;i++){
           temp[i] = arr[high];
       }
       while(low<=high){
           mid = low + f[k-1] - 1;
           if (target<temp[mid]){
               high = mid-1;
               k--;
           }else if (target>temp[mid]){
               low = mid + 1;
               k-=2;
           }else {
               if (mid<=high){
                   return mid;
               }else {
                   return high;
               }
           }
       }
       return  -1;
    }
    }