二分查找的总结(6种变形)

Posted on | In |
Words count in article: 2.8k

二分查找的总结

普通的二分查找

最普通的写法:

  • 范围在[L,R]闭区间中，L = 0、R = arr.length - 1；
  • 注意循环条件为 L <= R ，而不是L < R；

这里写图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static int bs1(int[] arr,int key){
    int L = 0,R = arr.length - 1; //在[L,R]范围内寻找key
    int mid;
    while( L <= R){
        mid = L + (R - L) / 2;
        if(arr[mid] == key)
            return mid;
        if(arr[mid] > key)
            R = mid - 1;// key 在 [L,mid-1]内
        else
            L = mid + 1;
    }
    return -1;
}

普通二分查找的另一种写法

首先说明，这个和上面的二分查找是完全一样的，只不过我们定义的区间不同而已:

  • 上面的二分查找是在[L,R]的闭区间中查找，而这个二分查找是在[L,R)的左闭右开区间查找；

  • 所以此时的循环条件是L < R ，因为R本来是一个不可到达的地方，我们定义为了开区间，所以R是一个不会考虑的数，所以我们循环条件是L < R；

  • 同理，当arr[mid] > key的时候，不是R = mid - 1，因为我们定义的是开区间，所以R = mid ，因为不会考虑arr[mid]这个数；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//和上面的完全一样，只是一开始R不是arr.length-1 而是arr.length
static int bs2(int[] arr,int key){
    int L = 0, R = arr.length; //注意这里R = arr.length 所以在[L,R)开区间中找
    int mid;
    while( L < R){ //注意这里 不是 L <= R
        mid = L + (R - L)/2;
        if(arr[mid] == key)
            return mid;
        if(arr[mid] > key)
            R = mid; // 在[L,mid)中找
        else
            L = mid + 1;
    }
    return -1;
}

上面的两种方式一般还是第一种方式用的多一点。

第一个=key的，不存在返回-1

这个和之前的不同是:

  • 数组中可能有重复的key，我们要找的是第一个key的位置；

  • 和普通二分查找法不同的是在我们要R = mid - 1前的判断条件不是arr[mid] > key，而是arr[mid] >= key；

  • 为什么是上面那样，其实直观上理解，我们要找的是第一个，那我们去左边找的时候不仅仅arr[mid] > key就去左边找，等于我也要去找，因为我要最左边的等于的；

  • 最后我们要判断L是否越界(L 有可能等于arr.length)，而且最后arr[L]是否等于要找的key；

  • 如果arr[L]不等于key，说明没有这个元素，返回-1；

举个例子:

这里写图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**查找第一个与key相等的元素的下标，　如果不存在返回-1　*/
   static int firstEqual(int[] arr,int key){
       int L = 0, R = arr.length - 1; //在[L,R]查找第一个>=key的
       int mid;
       while( L <= R){
           mid = L + (R - L)/2;
           if(arr[mid] >= key)
               R = mid - 1;
           else
               L = mid + 1;
       }
       if(L < arr.length && arr[L] == key)
           return L;
       return -1;
   }

第一个>=key的

这个和上面那个寻找第一个等于key的唯一的区别就是:

  • 最后我们不需要判断( L < arr.length && arr[L] == key)，因为如果不存在key的话，我们返回第一个> key的元素即可；

  • 注意这里没有判断越界(L < arr.length )，因为如果整个数组都比key要小，就会返回arr.length的大小；

1
2
3
4
5
6
7
8
9
10
11
12
13
/**查找第一个大于等于key的元素的下标*/
   static int firstLargeEqual(int[] arr,int key){
       int L = 0, R = arr.length - 1;
       int mid;
       while( L <= R){
           mid = L + (R - L) / 2;
           if(arr[mid] >= key)
               R = mid - 1;
           else
               L = mid + 1;
       }
       return L;
   }

第一个>key的

这个和上两个的不同在于:

  • if(arr[mid] >= key) 改成了 if(arr[mid] > key)，因为我们不是要寻找 = key的；

  • 看似和普通二分法很像，但是我们在循环中没有判断if(arr[mid] == key)就返回mid(因为要寻找的不是等于key的)，而是在最后返回了L ；

举个例子:

这里写图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**查找第一个大于key的元素的下标 */
static int firstLarge(int[] arr,int key){
    int L = 0,R = arr.length - 1;
    int mid;
    while(L <= R){
        mid = L + (R - L) / 2;
        if(arr[mid] > key)
            R = mid - 1;
        else
            L = mid + 1;
    }
    return L;
}

第一个...的总结

上面写了三个第一个.....的程序，可以发现一些共同点 ，也可以总结一下它们微妙的区别:

  • 最后返回的都是L；

  • 如果是寻找第一个等于key的，是if( arr[mid] >= key) R = mid - 1，且最后要判断L 的合法以及是否存在key；

  • 如果是寻找第一个大于等于key的，也是if(arr[mid] >= key) R = mid - 1，但是最后直接返回L；

  • 如果是寻找第一个大于key的，则判断条件是if(arr[mid] > key) R = mid - 1，最后返回L ；

最后一个=key的，不存在返回-1

和寻找第一个 = key的很类似，不过是方向的不同而已:

  • 数组中有可能有重复的key，我们要查找的是最后一个 = key的位置，不存在返回-1；

  • 为了更加的直观的理解，和寻找第一个…的形成对比，这里是当arr[mid] <= key的时候，我们要去右边查找(L = mid + 1)，同样是直观的理解，因为我们是要去找到最后一个 = key的，所以不仅仅是arr[mid] < key要去左边寻找，等于key的时候也要去左边寻找；

  • 和第一个….不同的是，我们返回的都是R；

  • 同时我们也要判断R的下标的合法性，以及最后的arr[R]是否等于key，如果不等于就返回-1；

举个例子:

这里写图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**查找最后一个与key相等的元素的下标，　如果没有返回-1*/
static int lastEqual(int[] arr,int key){
    int L = 0, R = arr.length - 1;
    int mid;
    while( L <= R){
        mid = L + (R - L)/2;
        if(arr[mid] <= key)
            L = mid + 1;
        else
            R = mid - 1;
    }
    if(R >= 0 && arr[R] == key)
        return R;
    return -1;
}

最后一个<=key的

这个和上面那个寻找最后一个等于key的唯一的区别就是:

  • 最后我们不需要判断 (R >= 0 && arr[R] == key)，因为如果不存在key的话，我们返回最后一个 < key的元素即可；

  • 注意这里没有判断越界(R >= 0 )，因为如果整个数组都比key要大，数组最左边的更左边一个(也就是-1)；

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    /**查找最后一个小于等于key的元素的下标 */
    static int lastSmallEqual(int[] arr,int key){
        int L = 0, R = arr.length - 1;
        int mid;
        while( L <= R){
            mid = L + (R - L) / 2;
            if(arr[mid] <= key)
                L = mid + 1;
            else
                R = mid - 1;
        }
        return R;
    }

最后一个<key 的

这个和上面两个不同的是:

  • 和上面的程序唯一不同的就是arr[mid] <= key改成了 arr[mid] < key，因为我们要寻找的不是 = key的；

  • 注意这三个最后一个的都是先对L的操作L = mid + 1，然后在else 中进行对R的操作；

这里写图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**查找最后一个小于key的元素的下标*/
static int lastSmall(int[] arr,int key){
    int L = 0, R = arr.length - 1;
    int mid;
    while(L <= R){
        mid = L + (R - L) / 2;
        if(arr[mid] < key)
            L = mid + 1;
        else
            R = mid - 1;
    }
    return R;
}

最后一个...的总结

上面三个都是求最后一个.....的，也进行一下总结:

  • 最后返回的都是R；

  • 第一个if判断条件(不管是arr[mid] <= key还是arr[mid] < key) ，都是L的操作，也就是去右边寻找；

  • 如果是寻找最后一个 等于 key的， if(arr[mid] <= key) L = mid + 1; 不过最后要判断R的合法性以及是否存在key；

  • 如果是寻找最后一个 小于等于 key的，也是if(arr[mid] <= key) L = mid + 1；不过最后直接返回R；

  • 如果是寻找最后一个 小于 key的，则判断条件是 if(arr[mid] < key) L = mid + 1 ，最后返回R；

完整测试代码

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
public class BinarySearch {

    //最普通的二分搜索法
     static int bs1(int[] arr,int key){
        int L = 0,R = arr.length - 1; //在[L,R]范围内寻找key
        int mid;
        while( L <= R){
            mid = L + (R - L) / 2;
            if(arr[mid] == key)
                return mid;
            if(arr[mid] > key)
                R = mid - 1;// key 在 [L,mid-1]内
            else
                L = mid + 1;
        }
        return -1;
    }

    //和上面的完全一样，只是一开始R不是arr.length-1 而是arr.length
     static int bs2(int[] arr,int key){
        int L = 0, R = arr.length; //注意这里R = arr.length 所以在[L,R)开区间中找
        int mid;
        while( L < R){ //注意这里 不是 L <= R
            mid = L + (R - L)/2;
            if(arr[mid] == key)
                return mid;
            if(arr[mid] > key)
                R = mid; // 在[L,mid)中找
            else
                L = mid + 1;
        }
        return -1;
    }


    /**查找第一个与key相等的元素的下标，　如果不存在返回-1　*/
     static int firstEqual(int[] arr,int key){
        int L = 0, R = arr.length - 1; //在[L,R]查找第一个>=key的
        int mid;
        while( L <= R){
            mid = L + (R - L)/2;
            if(arr[mid] >= key)
                R = mid - 1;
            else
                L = mid + 1;
        }
        if(L < arr.length && arr[L] == key)
            return L;
        return -1;
    }

    /**查找第一个大于等于key的元素的下标*/
    static int firstLargeEqual(int[] arr,int key){
        int L = 0, R = arr.length - 1;
        int mid;
        while( L <= R){
            mid = L + (R - L) / 2;
            if(arr[mid] >= key)
                R = mid - 1;
            else
                L = mid + 1;
        }
        return L;
    }


    /**查找第一个大于key的元素的下标 */
    static int firstLarge(int[] arr,int key){
        int L = 0,R = arr.length - 1;
        int mid;
        while(L <= R){
            mid = L + (R - L) / 2;
            if(arr[mid] > key)
                R = mid - 1;
            else
                L = mid + 1;
        }
        return L;
    }


    /**查找最后一个与key相等的元素的下标，　如果没有返回-1*/
     static int lastEqual(int[] arr,int key){
        int L = 0, R = arr.length - 1;
        int mid;
        while( L <= R){
            mid = L + (R - L)/2;
            if(arr[mid] <= key)
                L = mid + 1;
            else
                R = mid - 1;
        }
        if(R >= 0 && arr[R] == key)
            return R;
        return -1;
    }

    /**查找最后一个小于等于key的元素的下标 */
    static int lastSmallEqual(int[] arr,int key){
        int L = 0, R = arr.length - 1;
        int mid;
        while( L <= R){
            mid = L + (R - L) / 2;
            if(arr[mid] <= key)
                L = mid + 1;
            else
                R = mid - 1;
        }
        return R;
    }


    /**查找最后一个小于key的元素的下标*/
    static int lastSmall(int[] arr,int key){
        int L = 0, R = arr.length - 1;
        int mid;
        while(L <= R){
            mid = L + (R - L) / 2;
            if(arr[mid] < key)
                L = mid + 1;
            else
                R = mid - 1;
        }
        return R;
    }


    public static void main(String[] args) {

        int[] arr = {1,3,4,6,6,6,6,6,6,8,9};

        System.out.println("----------general-----------");

        System.out.println(bs1(arr,3));//1
        System.out.println(bs2(arr,3));//1
        System.out.println(bs2(arr,6));//5


        System.out.println("-----------first------------");

        //第一个 =  的
        System.out.println(firstEqual(arr,6));//3

        //第一个　>= 的
        System.out.println(firstLargeEqual(arr,5));//3
        System.out.println(firstLargeEqual(arr,6));//3

        //第一个 > 的
        System.out.println(firstLarge(arr,6));//9

        System.out.println("------------last------------");

        //最后一个 =  的
        System.out.println(lastEqual(arr,6));//8

        // 最后一个 <= 的
        System.out.println(lastSmallEqual(arr,7));//8
        System.out.println(lastSmallEqual(arr,6));//8

        //最后一个 < 的
        System.out.println(lastSmall(arr,6));//2

    }
}

效果:
这里写图片描述

欢迎关注我们的公众号
© 2021 — 2024 true | Site words total count: 328.5k
Theme — NexT.Pisces v5.1.4
0%