三大查找演算法

1.二分查找（Binary Search）

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {-4, -1, 0, 1, 2, 4, 5, 6, 7, 10};
        System.out.println(binarySearch1(arr, 1, 0, arr.length - 1));
        System.out.println(binarySearch2(arr, 1, 0, arr.length - 1));
        int[] arr2 = {-4, -1, 0, 1, 2, 4, 4, 5, 6, 7, 10};
        System.out.println(binarySearch3(arr2, 4, 0, arr.length - 1));
    }

    //非遞歸寫法
    public static int binarySearch1(int[] arr, int key, int left, int right) {
        int mid;
        while (left <= right) {
            mid = (left + right) >> 1;
            if (key < arr[mid]) {
                right = mid - 1;
            } else if (key > arr[mid]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    //遞歸寫法
    public static int binarySearch2(int[] arr, int key, int left, int right) {
        if (left > right) {
            return -1;
        }
        int mid = (left + right) >> 1;
        if (key < arr[mid]) {
            return binarySearch1(arr, key, left, mid - 1);
        } else if (key > arr[mid]) {
            return binarySearch1(arr, key, mid + 1, right);
        } else {
            return mid;
        }
    }

    //可查找重覆值
    public static ArrayList<Integer> binarySearch3(int[] arr, int key, int left, int right) {
        if (left > right) {
            return new ArrayList<>();
        }
        int mid = (left + right) >> 1;
        if (key < arr[mid]) {
            return binarySearch3(arr, key, left, mid - 1);
        } else if (key > arr[mid]) {
            return binarySearch3(arr, key, mid + 1, right);
        } else {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(mid);
            int index = mid - 1;
            //向左搜索
            while (true) {
                if (index < 0 || arr[index] != arr[mid]) {
                    break;
                }
                list.add(index);
                index--;
            }
            index = mid + 1;
            //向右搜索
            while (true) {
                if (index > arr.length - 1 || arr[index] != arr[mid]) {
                    break;
                }
                list.add(index);
                index++;
            }
            return list;
        }
    }
}

2.插值查找（InsertValue Search）

public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr = {-4, -1, 0, 1, 2, 4, 5, 6, 7, 10};
        System.out.println(insertValueSearch(arr, 1, 0, arr.length - 1));
    }

    public static int insertValueSearch(int[] arr, int key, int low, int high) {
        if (low > high) {
            return -1;
        }
        int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]);
        if (key < arr[mid]) {
            return insertValueSearch(arr, key, low, mid - 1);
        } else if (key > arr[mid]) {
            return insertValueSearch(arr, key, mid + 1, high);
        } else {
            return mid;
        }
    }
}

3.斐波那契查找（Fibonacci Search）

public class FibonacciSearch {
    private static final int size = 20;

    public static void main(String[] args) {
        int[] arr = {-4, -1, 0, 1, 2, 4, 5, 6, 7, 10};
        System.out.println(fibonacciSearch(arr, -4));
    }

    public static int fibonacciSearch(int[] arr, int key) {
        int len = arr.length;
        int low = 0;
        int mid = 0;
        int high = len - 1;
        int n = 0;
        int[] f = getFib();
        //找到等於或剛剛大於high的斐波那契值
        while (len > f[n] - 1) {
            n++;
        }
        //創建一個長度為f[n]-1的臨時數組，超出arr長度的部分用最後一個元素補齊
        int[] temp = Arrays.copyOf(arr, f[n] - 1);
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }
        System.out.println(Arrays.toString(temp));
        while (low <= high) {
            //mid = low + f[n - 1] - 1
            mid = low + f[n - 1] - 1;
            //f[n] = f[n - 1] + f[n - 2]
            //總 = 前 + 後
            if (key < temp[mid]) {
                high = mid - 1;
                n -= 1;
            } else if (key > temp[mid]) {
                low = mid + 1;
                n -= 2;
            } else {
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }

    public static int[] getFib() {
        int[] f = new int[size];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < size; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }
}