[数据结构与算法]算法：二分查找、插值查找、斐波那契查找

?

public class 二分查找 {
    public static void main(String[] args) {
        int[] arr = {4, 9, 12, 16, 16, 16, 16, 16, 20, 33, 34, 56, 77};
//        ArrayList<Integer> list = binarySearch3(arr, 16, 0, arr.length - 1);
//        System.out.println(list);
        int i = binarySearch2(arr, 16, 0, arr.length - 1);
        System.out.println(i);
    }

    public static int binarySearch(int[] arr, int findVal, int start, int end) {
        if (start <= end) {
            int midIndex = (start + end) / 2;
            int mid = arr[midIndex];
            if (findVal < mid) {
                return binarySearch(arr, findVal, start, midIndex - 1);
            } else if (findVal > mid) {
                return binarySearch(arr, findVal, midIndex + 1, end);
            } else if (findVal == mid) {
                return midIndex;
            }
        }
        return -1;
    }

    public static int binarySearch2(int[] arr, int findVal, int start, int end) {
        while (start <= end) {
            int midIndex = (start + end) / 2;
            int mid = arr[midIndex];
            if (findVal < mid) {
                end = mid - 1;
            } else if (findVal > mid) {
                start = mid + 1;
            } else if (findVal == mid) {
                return midIndex;
            }
        }
        return -1;
    }

    public static ArrayList<Integer> binarySearch3(int[] arr, int findVal, int start, int end) {
        if (start <= end) {
            int midIndex = (start + end) / 2;
            int mid = arr[midIndex];
            if (start > end) {
                System.out.println("没有找到");
                return new ArrayList<Integer>();
            }
            if (findVal < mid) {
                return binarySearch3(arr, findVal, start, midIndex - 1);
            } else if (findVal > mid) {
                return binarySearch3(arr, findVal, midIndex + 1, end);
            } else if (findVal == mid) {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(midIndex);
                int temp = midIndex - 1;
                while (findVal == arr[temp] && temp >= 0) {
                    list.add(temp);
                    temp--;
                }
                temp = midIndex + 1;
                while (findVal == arr[temp] && temp < arr.length) {
                    list.add(temp);
                    temp++;
                }
                return list;
            }
        }
        return null;
    }
}

?

public class 插值查找 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 3, 3, 3, 3, 3, 3, 4, 5, 6, 7, 8, 9, 10};
        int i = inserSearch2(arr, 6, 0, arr.length - 1);
        System.out.println(i);
        ArrayList<Integer> list=inserSearch3(arr,3,0,arr.length-1);
        System.out.println(list);

    }
    public static int inserSearch2(int[] arr, int key, int left, int right) {
        while (left <= right && key >= arr[0] && key <= arr[arr.length - 1]) {//防止数组越界
            int midIndex = left + (key - arr[left]) / (arr[right] - arr[left]) * (right - left);
            if (key > arr[midIndex]) {
                left=midIndex+1;
            } else if (key < arr[midIndex]) {
                right=midIndex-1;
            } else if (key == arr[midIndex]) {
                return midIndex;
            }
        }
        return -1;
    }

    public static int inserSearch(int[] arr, int key, int left, int right) {
        if (left <= right && key >= arr[0] && key <= arr[arr.length - 1]) {//防止数组越界
            int midIndex = left + (key - arr[left]) / (arr[right] - arr[left]) * (right - left);
            if (key > arr[midIndex]) {
                return inserSearch(arr, key, midIndex + 1, right);
            } else if (key < arr[midIndex]) {
                return inserSearch(arr, key, left, midIndex - 1);
            } else if (key == arr[midIndex]) {
                return midIndex;
            }
        }
        return -1;
    }


    public static ArrayList<Integer> inserSearch3(int[] arr, int key, int left, int right) {
        if (left <= right && key >= arr[0] && key <= arr[arr.length - 1]) {//防止数组越界
            int midIndex = left + (key - arr[left]) / (arr[right] - arr[left]) * (right - left);
            if (key > arr[midIndex]) {
                return inserSearch3(arr, key, midIndex + 1, right);
            } else if (key < arr[midIndex]) {
                return inserSearch3(arr, key, left, midIndex - 1);
            } else if (key == arr[midIndex]) {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(midIndex);
                int temp = midIndex - 1;
                while (arr[temp] == key && temp >= 0) {
                    list.add(temp);
                    temp--;
                }
                temp = midIndex + 1;
                while (arr[temp] == key && temp <= arr.length - 1) {
                    list.add(temp);
                    temp++;
                }
                return list;
            }
        }
        return null;
    }
}

?

?

public class 斐波那契查找 {
    public static void main(String[] args) {
        int[] arr = {4, 9, 12, 16, 20, 33, 34, 56, 77};
        int i = fibonacciSort(arr, 34);
        System.out.println(i);
    }

    public static int fibonacciSort(int[] arr, int key) {
        int[] F = fibonacciArray();
        //计算数组长度处于斐波那契数列的位置
        int i = 0;
        while (F[i] - 1 < arr.length) {
            i++;
        }
        int[] newArr = Arrays.copyOf(arr, F[i]);//数组扩容
        for (int x = arr.length; x < F[i]; x++) {//补齐后面
            newArr[x] = arr[arr.length - 1];
        }
        int left = 0;
        int right = arr.length - 1;
        while (left <= right && key >= arr[0] && key <= arr[arr.length - 1]) {
            int midIndex = left + F[i - 1] - 1;
            if (key > newArr[midIndex]) {
                left = midIndex + 1;
                i -= 2;
            } else if (key < newArr[midIndex]) {
                right = midIndex - 1;
                i -= 1;
            } else if (key == newArr[midIndex]) {
                return Math.min(midIndex, arr.length - 1);
            }
        }
        return -1;
    }

    public static int[] fibonacciArray() {
        int[] arr = new int[10];
        arr[0] = 1;
        arr[1] = 1;
        int i = 2;
        while (i < 10) {
            arr[i] = arr[i - 1] + arr[i - 2];
            i++;
        }
        return arr;
    }

?