查找算法

二分查找

1. 有序数组进行二分查找

2. 二分查找有两种 一种是递归，一种 是非递归

3. 二分查找的思路分析

   1. 首先确定该数组的中间的下标 mid =(left+right)/2
   2. 接着让需要查找的数findVal和arr[mid]比较
   3. findVal > arr[mid] 说明要找的数在mid右边，需要向右递归查找，findVal < arr[mid] 说明要找的数在mid左边，需要向左递归查找 findVal=arr[mid]说明找到，就返回
   4. 当 left>right就需要退出

4. 代码实现

   public class BinarySearch {
       public static void main(String[] args) {
           int arr[] = {1,8,10,89,1000,1234};
   
           System.out.println(binarySearch(arr, 0, arr.length-1, 88));
       }
       //二分查找
       public static int binarySearch(int[] arr, int left,int right,int findVal){
           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;
           }
   
       }
   }

5. 找到数组中相同的所有的值 并返回下标

   public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int findVal){
       if (left > right){
           return new ArrayList<Integer>();
       }
       int mid = (left+right)/2;
       int midVal =arr[mid];
       if (findVal > midVal) {//向右递归
           return binarySearch2(arr, mid+1, right, findVal);
       }else  if (findVal < midVal){
           return  binarySearch2(arr, left, mid-1, findVal);
       }else {
           ArrayList<Integer> list =new ArrayList<Integer>();
           int temp = mid - 1;
           while (true){
               if (temp <0 || arr[temp]!=findVal){
                   break;
               }
               list.add(temp);
               temp-=1;
           }
           list.add(mid);
      
           temp = mid +1;
           while (true){
               if(temp >arr.length-1 ||arr[temp] != findVal){
                   break;
               }
               list.add(temp);
               temp += 1;
           }
           return list;
       }
      
   }
      

插值查找

1. 插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。
2. 公式为 int mid = left +（right - left) *(findVal -arr[left])/(arr[right] -arr[left])

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

代码实现

import java.util.Arrays;

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(fibSearch(arr, 1234));
    }

    //因为后面我们 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的长度，因此我们需要使用Arrays类，构建一个新的数组，并指向a[]
        //不足的部分会使用0填充
        int[] temp = Arrays.copyOf(a,f[k]);
        //实际上需求使用a数组最后的数值填充temp\
        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;
                k--;
            } else if (key > temp[mid]) {
                low = mid + 1;
                k -= 2;
            } else { //找到
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }
}