java实现4种查找算法

1.直接查找（暴力匹配）

public class Violence {
    public static void main(String[] args) {
        int [] arr={2,3,4,5,6,1,12,23};
        int search = search(1, arr);
        System.out.println(search);
    }
    public static int search(int n,int[] arr){
        for (int i=0;i<arr.length;i++){
            if(arr[i]==n){
                return i;
            }
        }
        return -1;
    }
}

2.二分法

二分法的mid=（left+right）/2，然后递归

递归方法

 /*
 二分查找的数组必须是有序的
 找到返回下标，没找到返回-1
 在数组中没有重复的数字
  */
 public static int  searchIndex(int []arr,int left,int right,int SearchVal){
     int mid=(left+right)/2;
     int minVal=arr[mid];
     if(left>right){
         return -1;
     }
      if(SearchVal>minVal){
        return   searchIndex(arr,mid+1,right,SearchVal);
      }else if(SearchVal<minVal){
       return    searchIndex(arr,left,mid-1,SearchVal);
      }else {
          return mid;
      }
 }

非递归

/*
非递归二分查找
 */
public static int binarySearch(int[] arr,int value){
    int left=0;
    int right=arr.length-1;
    while (left<right){
        int mid = (left+right)/2;
        if(arr[mid]==value){
            return mid;
        }else if(arr[mid]<value){
            right=mid+1;
        }else {
            left=mid-1;
        } 
    }
    return -1;
}

用二分查找递归的方式查找有重复的数字

/*
在数组中有重复的数字；
 */
public static ArrayList<Integer> searchIndex2(int []arr, int left, int right, int SearchVal){
    int mid=(left+right)/2;
    int minVal=arr[mid];
    if(left>right){
        return new ArrayList<>();
    }
    if(SearchVal>minVal){
        return   searchIndex2(arr,mid+1,right,SearchVal);
    }else if(SearchVal<minVal){
        return    searchIndex2(arr,left,mid-1,SearchVal);
    }else {
        //return mid;
        ArrayList<Integer> list = new ArrayList<>();
        //temp想左扫描
        int temp = mid-1;
        while (true){
            if(temp<0 || arr[temp]!=SearchVal){
                break;
            }
            list.add(temp);
            temp--;
        }
        list.add(mid);
        int temps = mid+1;
        while (true){
            if(temps>right ||arr[temps]!=SearchVal){
                break;
            }
            list.add(temps);
            temps++;
        }
        return list;
    }
}

3.插值查找

思想：就是将二分法的mid=（left+right）/2，变成mid=left+(right-left)*()(key-arr[left])/(arr[right]-arr[left]))然后递归

/*
插值查找
 */
public static int InsertSearch(int []arr,int left,int right,int findVal){
    if(left>right || findVal<arr[0] || findVal>arr[arr.length-1]){
        return -1;
    }
    int mid = left +(right-left)*((findVal-arr[left])/(arr[right]-arr[left]));
    int midVal = arr[mid];
    if(findVal>midVal){
       return InsertSearch(arr,mid+1,right,findVal);
    }else if(findVal<midVal){
      return   InsertSearch(arr,left,mid-1,findVal);
    }else {
        return mid;
    }
}

4.斐波那契数列查找（黄金分割率）

//斐波那契查找算法
public class Fibonacci {
    public static int Maxsize = 20;

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 12, 15};
        int val = findVal(arr, 12);
        System.out.println(val);

    }

    //用函数定义一个斐波那契数列
    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 findVal(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        int f[] = fib();// 调用的斐波那契数列
        int k = 0;//斐波那契数列所以
        int mid = 0;
        while (high > f[k]) {
            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 (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;
    }
}