有序表的查找

折半查找：线性表必须采用顺序存储。在有序表中，去中间记录作为比较对象，若给定值与中间记录相等，则查找成功；若给定值小于中间记录，则在中间记录的左半区继续折半查找；若给定值大于中间记录，则在中间记录的右半区继续折半查找。不断重复上述过程，直到查找成功或者查找区域无记录，即查找失败为止。

/**
     * 折半查找
     * @param a 数组        
     * @param key  待查找的值      
     * @return 待查找的值在数组中的下标，查找失败返回-1
     */
    public static int Binary_Search(int[] a, int key) {
        int low, mid, high;
        low = 0;
        high = a.length - 1;
        while (low <= high) {
            mid = (high + low) / 2;
            if (key < a[mid]) {
                high = mid - 1;
            } else if (key > a[mid]) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

---

插值查找：插值查找是根据要查找的关键字与查找表中最大最小记录比较后的查找方法，与折半查找的区别主要在于mid的计算方式。插值查找适用于表长较大且关键字分布较均匀的查找表。
mid = low + (high - low) * (key - a[low]) / (a[high] - a[low])）
其中key为要查找的关键字；a为有序表。

    /**
     * 插值查找，与折半查找的不同仅在于mid的计算方式
     * @param a  数组       
     * @param key 待查找的值    
     * @return 待查找的值在数组中的下标，查找失败返回-1
     */
    public static int InsertValue_Search(int[] a, int key) {
        int low, mid, high;
        low = 0;
        high = a.length - 1;
        while (low <= high) {
            mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]);
            if (key < a[mid]) {
                high = mid - 1;
            } else if (key > a[mid]) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

---

斐波拉契查找：使用黄金分割原理来选择mid，斐波拉契数列中前一个数除以相邻的后一个数，比值无限接近黄金分割（约等于0.618）。

    // 斐波拉契查找
    public static int Fibonacci_Search(List<Integer> a, int key) {
        int n = a.size() - 1;
        int[] fibonacci = new int[a.size()];
        fibonacci[0] = 0;
        fibonacci[1] = 1;
        // 初始化斐波拉契数组
        for (int i = 2; i < a.size(); i++) {
            fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
        }
        int low, mid, high, k;
        low = 0;
        high = n;
        k = 0;
        // 获取有序数组a的最大下标在斐波拉契数组中的位置
        while (n > fibonacci[k] - 1) {
            k++;
        }
        // 将不满的数值补全，避免出现空值查询
        for (int i = n; i < fibonacci[k] - 1; i++) {
            // 使用数组的最后一个数值补全数组，保持数组有序
            a.add(a.get(n));
        }
        while (low <= high) {
            mid = low + fibonacci[k - 1] - 1;
            if (key < a.get(mid)) {
                high = mid - 1;
                k = k - 1;
            } else if (key > a.get(mid)) {
                low = mid + 1;
                k = k - 2;
            } else {
                if (mid <= n) {
                    return mid;
                } else {
                    return n;
                }
            }
        }
        return -1;
    }

---

测试程序：

        int[] arr = { 0, 2, 3, 5, 7, 9, 12, 16, 19, 21, 23 };
        List<Integer> a = new ArrayList<>();
        a.add(0);
        a.add(2);
        a.add(3);
        a.add(5);
        a.add(7);
        a.add(9);
        a.add(12);
        a.add(16);
        a.add(19);
        a.add(21);
        a.add(23);

        System.out.println("折半查找7：" + Binary_Search(arr, 7));
        System.out.println("插值查找7：" + InsertValue_Search(arr, 12));
        System.out.println("斐波拉契查找23：" + Fibonacci_Search(a, 23));

测试结果：

有序表查找结果.png