查询算法_查分算法举例

查询算法

顺序查询

顺序查询可以是有序也可以是无序

二分查询

二分查询必须是有序

    /***
     *时间复杂度最好o(logn),最差o(log(n+1))
     * 空间复杂度 o(1)
     * @return
     */
    public int binearySearch(int[] num, int val) {
        int low = 0;
        int hight = num.length - 1;
        while (low < hight) {
            int mid = (low + hight) / 2;
            if (num[mid] == val) {
                return mid;
            }
            // 目标数据比中间数据大，在中间数据左边
            if (val > num[mid]) {
                low = mid + 1;
            }
            // 目标数据比中间数据小，在中间数据右边
            if (val < num[mid]) {
                hight = mid - 1;
            }
        }
        return -1;
    }
    

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

插值查询

适用于有序，且数值分布比较均匀的情况下使用
与二分法查找相似
只是中间值的计算方式不一样

left+((x-n[left])/n[right]-n[left])*(right-left)

  /***
     *插值查询
     *
     * 与二分查找类似
     * 特点：有序，而且呈现均匀分布特征的可以是使用
     *时间复杂度:o(logn)   空间复杂度o(1)
     *
     * mid = left+((x-n[left])/n[right]-n[left])*(right-left)
     *
     * @return
     */
    public int interlolationSearch(int[] num, int val) {
        int left = 0;
        int right = num.length - 1;

        while (left < right) {
            int mid = left + ((val - num[left]) / num[right] - num[left]) * (right - left);
            if (val == num[mid]) {
                return mid;
            }

            if (val > num[mid]) {
                left = mid + 1;
            }

            if (val < num[mid]) {
                right = mid - 1;
            }
        }

        return -1;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

斐波那契查找

斐波那契查找的时间复杂度还是O(log2n)，但是与折半查找相比，斐波那契查找的优点是它只涉及加法和减法运算，而不用除法，而除法比加减法要占用更多的时间，因此，斐波那契查找的运行时间理论上比折半查找小，但是还是得视具体情况而定

 private int fib(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }

    /**
     * 使用黄金分割点进行分割
     *
     * @param num
     * @return
     */
    public int fibSearch(int[] num, int val) {
        int low = 0;
        int high = num.length - 1;

        int k = 0;
        // 确定k的大小
        while (high > fib(k) - 1) {
            k++;
        }

        // 创建一个确定fib(k)大小的数组
        //
        int[] temp = Arrays.copyOf(num, fib(k));

        // 对超出原数组长度的元素填充为原数组的最有一个数子

        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = num[high];
        }

        while (low < high) {
            int mid = low + fib(k - 1) - 1;

            if (val < temp[mid]) {
                high = mid - 1;
                // f(k)=f(k-1)+f(k-2)
                //数据在左边部分
                k--;
            } else if (val > temp[mid]) {
                low = mid + 1;
                // f(k)=f(k-1)+f(k-2)
                // 数据在右边部分
                k -= 2;
            } else {
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }

        return -1;
    }
    
    

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65