数据结构与算法-俩分法查找

Posted on | Edited on | In ,

俩分法的时间复杂度

效率很高，时间复杂度是O(logN)。但是条件也比较苛刻

  1. 必须是有序数组的，支持通过下表随机访问。如果用链表会退化成时间复杂度O(n)
  2. 数组必须有序，所以在查找前需要对数组进行排序，
  3. 数量太小不适合二分查找法。因为在数据量小的时候LogN不见得比遍历数组要快
  4. 数量太大不适合二分查找法，因为数组要申请一片连续空间的内存如果太大，可能内存会不够用。

二分查找法的俩种实现方式

递归

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
public int search(int[] a, int dest) {
    int l = 0;
    int h = a.length - 1;

    if (l == h) {
        return a[l] == dest ? l : -1;
    }

    //开始查找每次取出一半
    return search(a, l, h, dest);
}

private int search(int[] a, int l, int h, int dest) {
    if (l >= h) {
        return a[l] == dest ? l : -1;
    }

    //取中点，如果==跳出递归，如果a[mid]>dest 下一次就是l--mid-1，反之下一次是mid+1,high
    int mid = l + ((h - l) >> 1);
    if (a[mid]==dest){
        return mid;
    }else if(a[mid]>dest){
        return search(a,l,mid-1,dest);
    }else{
        //a[mid]<dest
        return search(a,mid+1,h,dest);
    }
}

循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int search(int[] a, int dest) {
    int l = 0;
    int h = a.length - 1;

    if (l == h) {
        return a[l] == dest ? l : -1;
    }

    //循环查找
    while (l <= h) {
        int mid = l + (h - l) / 2;
        if (a[mid] == dest) {
            return mid;
        } else if (a[mid] < dest) {
            l=mid+1;
        }else{
           h=mid-1;
        }

    }
    return -1;
}

例子：算一个数的平方跟

这到例子主要是讲解，二分法的解决思路，先确认查找范围x比1大1–x,如果x在0和1之间0–1,然后用二分法求解mid最接近结果。

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
public double squart(double x, int n) {
    //快速返回
    if (x == 0 || x == 1) {
        return x;
    }

    double l = 1;
    double h = x;
    //如果x在0->1之间
    if (x > 0 && x < 1) {
        l = 0;
        h = 1;
    }

    long base = 1;
    int i = 1;
    while (i <= n) {
        base = base * 10;
        i++;
    }
    //递归调用
    double ret = squart(x, l, h, 1.00f / base);

    return new BigDecimal(ret).setScale(n, BigDecimal.ROUND_HALF_UP).doubleValue();
}

//二分查找
private double squart(double x, double l, double h, float p) {
    if (l >= h) {
        return l;
    }

    double mid = l + (h - l) / 2;

    if (mid * mid > x) {
        return squart(x, l, mid, p);
    } else if (mid * mid < x) {
        return squart(x, mid, h, p);
    } else {
        return mid;
    }

}

二分法变形查找

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112


public static int searchLastEq(int a[], int d) {
    int l = 0;
    int h = a.length - 1;

    while (l <= h) {
        int m = l + ((h - l) >> 1);
        if (a[m] > d) {
            h = m - 1;
        } else if (a[m] < d) {
            l = m + 1;
        } else {
            //注意找最后一个eq所以如果相等就判断后一位是否相等如果不相等返回，如果相等，说明要取的值在右边，l=m+1
            if (m == a.length - 1 || a[m + 1] != d) {
                System.out.printf("最后个相等%s的Index=%s,v=%s\n", d, m, a[m]);
                return m;
            }
            l = m + 1;
        }
    }

    System.out.println("最后一个相等的没找到");
    return -1;
}

public static int searchFirstEq(int a[], int d) {
    int l = 0;
    int h = a.length - 1;

    while (l <= h) {
        int m = l + ((h - l) >> 1);
        if (a[m] > d) {
            h = m - 1;
        } else if (a[m] < d) {
            l = m + 1;
        } else {
            //注意找第一个eq所以如果相等就判断前一位是否相等如果不相等返回，如果相等，说明要取的值在左边，h=m-1
            if (m == 0 || a[m - 1] != d) {
                System.out.printf("第一个相等%s的Index=%s,v=%s\n", d, m, a[m]);
                return m;
            }
            h = m - 1;
        }
    }

    System.out.println("第一个相等的没找到");
    return -1;
}

/**
 * ..a[m]...6,7,d,9.....-->7
 *
 * @param a
 * @param d
 * @return
 */
public static int searchRecentLte(int a[], int d) {
    int l = 0;
    int h = a.length;

    while (l <= h) {
        int m = l + ((h - l) >> 1);

        //如题，找d左边的第一值，当a[m]<=d的时候说明m在左边，然后一直往右边找，直到找到后面大于d的返回，
        // 如果右边依然<=d，说明要找的值还在右边，二分法l=m+1
        // 如果a[m]>d，不符合条件说明要找的值在m的左边，需要h=m-1
        if (a[m] <= d) {
            if (m == 0 || a[m + 1] > d) {
                System.out.printf("最后(最近的小于等于)小于等于%s的数的(Index=%s,v=%s)\n", d, m, a[m]);
                return m;
            }
            l = m + 1;
        } else {
            h = m - 1;
        }

    }
    return -1;
}

/**
 * .....6,7,d,9..a[m]...-->9
 *
 * @param a
 * @param d
 * @return
 */
public static int searchRecentGte(int a[], int d) {
    int l = 0;
    int h = a.length - 1;

    while (l <= h) {
        int m = l + ((h - l) >> 1);
        //如题：找d右边的第一个值，如果a[m]>=d，要一直向左找，找到m==0或者m的左边小于d的数，返回m
        // 如果a[m-1]依然大于d，说明要照的数在左边，h=m-1
        // 如果a[m]<d，说明要照的数在右边，l=m+1
        if(a[m]>=d){
            if(m==0|| a[m-1]<d){
                System.out.printf("第一个(最近的大于等于)大于等于%s的数的(Index=%s,v=%s)\n", d, m, a[m]);
                return m;
            }
            h=m-1;
        }else{
            //a[m]<d
            l=m+1;
        }

    }

    return -1;
}

课后作业-leetcode33

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
    public static void main(String[] args) {
        int[] a = new int[]{4, 5, 6, 7, 0, 1, 2};
        int target = 5;
        System.out.println(search(a, target));
    }

    public static int search(int[] a, int d) {
        int l = 0;
        int h = a.length - 1;


        while (l <= h) {
            if (a[l] == d) {
                return l;
            }
            if (a[h] == d) {
                return h;
            }
            int m = l + ((h - l) >> 1);
            if (a[m] == d) {
                return m;
            }
            if (a[m] > a[l]) {
                if (a[m] > d) {
                    if (a[l] < d) {
                        h = m - 1;
                    } else {
                        l = m + 1;
                    }
                } else {
//                    a[m]<d
                    l = m + 1;
                }
            } else {
                //a[m]<a[l]
                if (a[m] > d) {
                    h = m - 1;
                } else {
                    //a[m]<d
                    if (a[h] > d) {
                        l = m + 1;

                    } else {
                        h = m - 1;
                    }
                }
            }
        }
        return -1;
    }