二分查找的各种变形总结

发表于 | 分类于 | 评论数： | 阅读次数：
本文字数： 24k | 阅读时长 ≈ 22 分钟

其实，二分查找看起来so easy，但它的各种变形扣边界真的需要总结一下。

注意：以下代码均采用左右均为闭区间，即hi为最后一个元素下标，而不是元素个数。

base case

无重复数字，找target的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 1.1 无重复数字，二分查找出target的下标
 */
public static int binarySearchWithoutDuplicates(int[] nums, int target) {
    if (nums == null || nums.length <= 0) {
        return -1;
    }
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + ((hi - lo) >> 1);
        // 若target < nums[mid]，在左半段，在[lo, mid - 1]中找
        if (target < nums[mid]) {
            hi = mid - 1;
            // 若target > nums[mid]，在右半段，在[mid + 1, hi]中找
        } else if (target > nums[mid]) {
            lo = mid + 1;
        } else {
            return mid;
        }
    }
    // 未找到
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 递归版
		public static int binarySearchWithoutDuplicates2(int[] nums, int target) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }
        return helper(nums, target, 0, nums.length - 1);
    }

    public static int helper(int[] nums, int target, int lo, int hi) {
        if (lo > hi) {
            return -1;
        }
        int mid = lo + ((hi - lo) >> 1);
        if (target < nums[mid]) {
            return helper(nums, target, lo, mid - 1);
        } else if (target > nums[mid]) {
            return helper(nums, target, mid + 1, hi);
        } else {
            return nums[mid];
        }
    }

查找>=target的最小下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 1.2 查找第一个大于等于某个数的下标
 * 例：int[] a = {1,2,2,2,4,8,10}，查找2，返回第一个2的下标1；
 * 查找3，返回4的下标4；查找4，返回4的下标4。如果没有大于等于target的元素，返回-1。
 */
public static int binarySearchForFirstGreaterOrEqualNumIndex(int[] nums, int target) {
    if (nums == null || nums.length <= 0) {
        return -1;
    }
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + ((hi - lo) >> 1);
        // target < nums[mid]，target在左半段，
        // 如果target==nums[mid]，虽然hi = mid - 1，但是最后在左半段没有找到更小的，最后会返回mid，如{0,1,1,2,4,8,10}
        if (target <= nums[mid]) {
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    // 如果target大于数组最后一个元素，lo最后变为nums.length，即没有元素大于target，需要返回-1。
    return lo <= nums.length - 1 ? lo : -1;
}

查找<=target的最大下标

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
/**
 * 1.3 从右边起查找第一个小于等于某个数的下标
 * 例，int[] a = {1,2,2,2,4,8,10}，查找2，返回最后一个2的下标3；查找3，返回最后一个2的下标3；
 * 查找4，返回4的下标4。如果没有<=target的元素，返回-1。
 */
public static int binarySearchForFirstLessOrEqualNumIndex(int[] nums, int target) {
    if (nums == null || nums.length <= 0) {
        return -1;
    }
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + ((hi - lo) >> 1);
        // target < nums[mid]，target在左半段
        if (target < nums[mid]) {
            hi = mid - 1;
            // target > nums[mid]，target在右半段，
            // 如果target==nums[mid]，虽然lo = mid + 1，但是最后在右半段没有找到更大的，target < nums[mid]，hi会返回前一个数，如{0,1,1,2,4,8,10}
        } else {
            lo = mid + 1;
        }
    }
    // 如果target小于数组第一个元素，hi最后变为-1，即没有元素<=target，需要返回-1。
    // hi = lo - 1
    return hi >= 0 ? hi : -1;
}

base case上的改进

查找>target的最小下标

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
/**
 * 【1.3的改进：1.3的下一个数就是1.4的结果】
 * 1.4 查找第一个大于某个数的下标
 * 注意：第一个小于等于某个数的下一个数就是第一个大于某个数的数
 * 例：int[] a = {1,2,2,2,4,8,10}，查找2，返回4的下标4；
 * 查找3，返回4的下标4；查找4，返回8的下标5。如果没有大于key的元素，返回-1。
 * 第一个小于等于2的数的下标是3，第一个大于2的数的下标是4
 */
public static int binarySearchForFirstGreaterNumIndex(int[] nums, int target) {
    if (nums == null || nums.length <= 0) {
        return -1;
    }
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + ((hi - lo) >> 1);
        // target < nums[mid]，target在左半段，
        if (target < nums[mid]) {
            hi = mid - 1;
            // target >= nums[mid]， 第一个大于target的数在右半段
        } else {
            lo = mid + 1;
        }
    }
    // 如果target大于数组最后一个元素，lo最后变为nums.length，即没有元素大于target，需要返回-1。
    return lo <= nums.length - 1 ? lo : -1;
}

查找<target的最大下标

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
/**
 * 【1.2的改进：1.2的前一个数就是1.5的结果】
 * 1.5 从右边起查找第一个小于某个数的下标
 * 例，int[] a = {1,2,2,2,4,8,10}，查找2，返回1的下标0；查找3，返回最后一个2的下标3；
 * 查找4，返回最后一个2的下标3。如果没有<target的元素，返回-1。
 */
public static int binarySearchForFirstLessNumIndex(int[] nums, int target) {
    if (nums == null || nums.length <= 0) {
        return -1;
    }
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + ((hi - lo) >> 1);
        // target < nums[mid]，target在左半段，
        // 如果target==nums[mid]，虽然hi = mid - 1，但是最后在左半段没有找到更小的，最后会返回mid，如{0,1,1,2,4,8,10}
        if (target <= nums[mid]) {
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    // 1.2 return lo <= nums.length - 1 ? lo : -1;
    // 如果target小于数组第一个元素，hi最后变为-1，即没有元素<=target，需要返回-1。
    // hi = lo - 1
    return hi >= 0 ? hi : -1;
}

查找target的最小下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 【1.2的改进：1.2最后的返回加一个判断条件】
 * 1.5 查找第一个等于某个数的下标
 * 例：int[] a = {1,2,2,2,4,8,10}，查找2，返回第一个2的下标1；
 * 查找4，返回4的下标4。如果没有等于target的元素，返回-1。
 */
public static int findLeftIndex(int[] nums, int target) {
    if (nums == null || nums.length <= 0) {
        return -1;
    }
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + ((hi - lo) >> 1);
        // target < nums[mid]，target在左半段，
        // 如果target==nums[mid]，虽然hi = mid - 1，但是最后在左半段没有找到更小的，最后会返回mid，如{0,1,1,2,4,8,10}
        if (target <= nums[mid]) {
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    // 如果target大于数组最后一个元素，lo最后变为nums.length，即没有元素大于target，需要返回-1。
    return lo <= nums.length - 1 && nums[lo] == target ? lo : -1;
}

不基于前面的直接写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int findLeftIndex2(int[] nums, int target) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + ((hi - lo) >> 1);
            // 关注第一个=target的数，处于较为前面的位置
            // <= nums[mid]
            if (target < nums[mid]) {
                hi = mid - 1;
            } else if (target > nums[mid]) { // > nums[mid]
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return nums[lo] == target ? lo : -1;
    }

查找target的最大下标

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
/**
 * 【1.3的改进：1.3最后的返回加一个判断条件】
 * 1.6 查找最后一个等于某个数的下标，即从右边起查找第一个等于某个数的下标
 * 例，int[] a = {1,2,2,2,4,8,10}，查找2，返回最后一个2的下标3
 * 查找4，返回4的下标4。如果没有<=target的元素，返回-1。
 */
public static int findRightIndex(int[] nums, int target) {
    if (nums == null || nums.length <= 0) {
        return -1;
    }
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + ((hi - lo) >> 1);
        // target < nums[mid]，target在左半段
        if (target < nums[mid]) {
            hi = mid - 1;
            // target > nums[mid]，target在右半段，
            // 如果target==nums[mid]，虽然lo = mid + 1，但是最后在右半段没有找到更大的，target < nums[mid]，hi会返回前一个数，如{0,1,1,2,4,8,10}
        } else {
            lo = mid + 1;
        }
    }
    // 如果target小于数组第一个元素，hi最后变为-1，即没有元素<=target，需要返回-1。
    // hi = lo - 1
    return hi >= 0 && nums[hi] == target ? hi : -1;
}

不基于前面的直接写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int findRightIndex2(int[] nums, int target) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }
        int lo = 0, hi = nums.length - 1;
        while (lo < hi - 1) {
            int mid = lo + ((hi - lo) >> 1);
            if (target < nums[mid]) {
                hi = mid - 1;
            } else if (target > nums[mid]) {
                lo = mid + 1;
            } else {
                lo = mid;
            }
        }
        if (nums[hi] == target) {
            return hi;
        } else if(nums[lo] == target) {
            return lo;
        } else {
            return -1;
        }
    }

查找target出现的次数

1
2
3
4
5
6
7
8
9
/**
  * 【1.5和1.6的改进】
  * 1.7 查找一个数出现的次数
  */
 public static int getCount(int[] nums, int target) {
     int leftIndex = findLeftIndex(nums, target);
     int rightIndex = findRightIndex(nums, target);
     return rightIndex - leftIndex + 1;
 }

有序数组断成两节互换位置后查找最小值的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 【1.1的改进】
 * 1.8 把排序好的数组分成两部分，两部分互换顺序
 * 在有序数组断节后找到min数的index
 */
public static int findMinIndex(int[] nums) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + ((hi - lo) >> 1);
        // mid < hi：最小值在左半部分,也可能是自己
        if (nums[mid] < nums[hi]) {
            hi = mid;
            // mid > hi：最小值在右半部分，不可能是自己了
        } else if (nums[mid] > nums[hi]) {
            lo = mid + 1;
        } else {
            return mid;
        }
    }
    return lo;
}

汇总和测试函数

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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
package array;

import java.util.Arrays;

import static common.GenerateRandomArray.*;
import static common.PrintArray.printArray;

public class BinarySearch {
    /**
     * 1.1 无重复数字，二分查找出target的下标
     */
    public static int binarySearchWithoutDuplicates(int[] nums, int target) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);
            // 若target < nums[mid]，在左半段，在[lo, mid - 1]中找
            if (target < nums[mid]) {
                hi = mid - 1;
                // 若target > nums[mid]，在右半段，在[mid + 1, hi]中找
            } else if (target > nums[mid]) {
                lo = mid + 1;
            } else {
                return mid;
            }
        }
        // 未找到
        return -1;
    }

    public static int binarySearchComparator(int[] nums, int target) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 1.2 查找第一个大于等于某个数的下标
     * 例：int[] a = {1,2,2,2,4,8,10}，查找2，返回第一个2的下标1；
     * 查找3，返回4的下标4；查找4，返回4的下标4。如果没有大于等于target的元素，返回-1。
     */
    public static int binarySearchForFirstGreaterOrEqualNumIndex(int[] nums, int target) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);
            // target < nums[mid]，target在左半段，
            // 如果target==nums[mid]，虽然hi = mid - 1，但是最后在左半段没有找到更小的，最后会返回mid，如{0,1,1,2,4,8,10}
            if (target <= nums[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        // 如果target大于数组最后一个元素，lo最后变为nums.length，即没有元素大于target，需要返回-1。
        return lo <= nums.length - 1 ? lo : -1;
    }

    /**
     * 1.3 从右边起查找第一个小于等于某个数的下标
     * 例，int[] a = {1,2,2,2,4,8,10}，查找2，返回最后一个2的下标3；查找3，返回最后一个2的下标3；
     * 查找4，返回4的下标4。如果没有<=target的元素，返回-1。
     */
    public static int binarySearchForFirstLessOrEqualNumIndex(int[] nums, int target) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);
            // target < nums[mid]，target在左半段
            if (target < nums[mid]) {
                hi = mid - 1;
                // target > nums[mid]，target在右半段，
                // 如果target==nums[mid]，虽然lo = mid + 1，但是最后在右半段没有找到更大的，target < nums[mid]，hi会返回前一个数，如{0,1,1,2,4,8,10}
            } else {
                lo = mid + 1;
            }
        }
        // 如果target小于数组第一个元素，hi最后变为-1，即没有元素<=target，需要返回-1。
        // hi = lo - 1
        return hi >= 0 ? hi : -1;
    }

    /**
     * 【1.3的改进：1.3的下一个数就是1.4的结果】
     * 1.4 查找第一个大于某个数的下标
     * 注意：第一个小于等于某个数的下一个数就是第一个大于某个数的数
     * 例：int[] a = {1,2,2,2,4,8,10}，查找2，返回4的下标4；
     * 查找3，返回4的下标4；查找4，返回8的下标5。如果没有大于key的元素，返回-1。
     * 第一个小于等于2的数的下标是3，第一个大于2的数的下标是4
     */
    public static int binarySearchForFirstGreaterNumIndex(int[] nums, int target) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);
            // target < nums[mid]，target在左半段，
            if (target < nums[mid]) {
                hi = mid - 1;
                // target >= nums[mid]， 第一个大于target的数在右半段
            } else {
                lo = mid + 1;
            }
        }
        // 如果target大于数组最后一个元素，lo最后变为nums.length，即没有元素大于target，需要返回-1。
        return lo <= nums.length - 1 ? lo : -1;
    }

    /**
     * 【1.2的改进：1.2的前一个数就是1.5的结果】
     * 1.5 从右边起查找第一个小于某个数的下标
     * 例，int[] a = {1,2,2,2,4,8,10}，查找2，返回1的下标0；查找3，返回最后一个2的下标3；
     * 查找4，返回最后一个2的下标3。如果没有<target的元素，返回-1。
     */
    public static int binarySearchForFirstLessNumIndex(int[] nums, int target) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);
            // target < nums[mid]，target在左半段，
            // 如果target==nums[mid]，虽然hi = mid - 1，但是最后在左半段没有找到更小的，最后会返回mid，如{0,1,1,2,4,8,10}
            if (target <= nums[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        // 1.2 return lo <= nums.length - 1 ? lo : -1;
        // 如果target小于数组第一个元素，hi最后变为-1，即没有元素<=target，需要返回-1。
        // hi = lo - 1
        return hi >= 0 ? hi : -1;
    }


    /**
     * 【1.2的改进：1.2最后的返回加一个判断条件】
     * 1.5 查找第一个等于某个数的下标
     * 例：int[] a = {1,2,2,2,4,8,10}，查找2，返回第一个2的下标1；
     * 查找4，返回4的下标4。如果没有等于target的元素，返回-1。
     */
    public static int findLeftIndex(int[] nums, int target) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);
            // target < nums[mid]，target在左半段，
            // 如果target==nums[mid]，虽然hi = mid - 1，但是最后在左半段没有找到更小的，最后会返回mid，如{0,1,1,2,4,8,10}
            if (target <= nums[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        // 如果target大于数组最后一个元素，lo最后变为nums.length，即没有元素大于target，需要返回-1。
        return lo <= nums.length - 1 && nums[lo] == target ? lo : -1;
    }

    /**
     * 【1.3的改进：1.3最后的返回加一个判断条件】
     * 1.6 查找最后一个等于某个数的下标，即从右边起查找第一个等于某个数的下标
     * 例，int[] a = {1,2,2,2,4,8,10}，查找2，返回最后一个2的下标3
     * 查找4，返回4的下标4。如果没有<=target的元素，返回-1。
     */
    public static int findRightIndex(int[] nums, int target) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);
            // target < nums[mid]，target在左半段
            if (target < nums[mid]) {
                hi = mid - 1;
                // target > nums[mid]，target在右半段，
                // 如果target==nums[mid]，虽然lo = mid + 1，但是最后在右半段没有找到更大的，target < nums[mid]，hi会返回前一个数，如{0,1,1,2,4,8,10}
            } else {
                lo = mid + 1;
            }
        }
        // 如果target小于数组第一个元素，hi最后变为-1，即没有元素<=target，需要返回-1。
        // hi = lo - 1
        return hi >= 0 && nums[hi] == target ? hi : -1;
    }

    /**
     * 【1.5和1.6的改进】
     * 1.7 查找一个数出现的次数
     */
    public static int getCount(int[] nums, int target) {
        int leftIndex = findLeftIndex(nums, target);
        int rightIndex = findRightIndex(nums, target);
        return rightIndex - leftIndex + 1;
    }

    public static int getCountComparator(int[] nums, int target) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }
        int count = 0;
        for (int num : nums) {
            if (num == target) {
                count++;
            }
        }
        return count;
    }

    /**
     * 【1.1的改进】
     * 1.8 把排序好的数组分成两部分，两部分互换顺序
     * 在有序数组断节后找到min数的index
     */
    public static int findMinIndex(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);
            // mid < hi：最小值在左半部分,也可能是自己
            if (nums[mid] < nums[hi]) {
                hi = mid;
                // mid > hi：最小值在右半部分，不可能是自己了
            } else if (nums[mid] > nums[hi]) {
                lo = mid + 1;
            } else {
                return mid;
            }
        }
        return lo;
    }

    public static int findMinIndexComparator(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return -1;
        }
        int minIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            minIndex = nums[i] < nums[minIndex] ? i : minIndex;
        }
        return minIndex;
    }

    public static int[] moveArray(int[] nums) {
        // [0, nums.length)
        int moveNum = (int) ((nums.length) * Math.random());
        int left = nums.length - moveNum;
        int[] res = new int[nums.length];
        // 把后面的搬到前面来
        for (int i = 0; i < left; i++) {
            res[i] = nums[i + moveNum];
        }
        for (int i = left; i < nums.length; i++) {
            res[i] = nums[i - left];
        }
        return res;
    }


    public static void main(String[] args) {
        int testTime = 50;
        int maxSize = 10;
        int maxValue = 10;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArrayWithoutDuplicates(maxSize, maxValue);
            Arrays.sort(arr1);
            arr1 = moveArray(arr1);
            int[] arr2 = copyArray(arr1);
            // random [0,1)
            // random * length [0,length)
            if (arr1.length <= 0) {
                continue;
            }
            // Collections.singletonList(arr1).forEach(x -> System.out.println(Arrays.toString(x) + " "));
            // printArray(arr1);
            if (findMinIndex(arr1) != findMinIndexComparator(arr2)) {
                succeed = false;
                System.out.print("nums[]: ");
                printArray(arr2);
                System.out.println("find:" + findMinIndex(arr1));
                System.out.println("true:" + findMinIndexComparator(arr2));
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }

    public static void main4(String[] args) {
        int testTime = 500000;
        int maxSize = 10;
        int maxValue = 10;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArrayWithDuplicates(maxSize, maxValue);
            Arrays.sort(arr1);
            int[] arr2 = copyArray(arr1);
            int target = 0;
            // random [0,1)
            // random * length [0,length)
            if (arr1.length <= 0) {
                continue;
            }
            target = arr1[(int) (Math.random() * arr1.length)];
            // Collections.singletonList(arr1).forEach(x -> System.out.println(Arrays.toString(x) + " "));
            if (getCount(arr1, target) != getCountComparator(arr2, target)) {
                succeed = false;
                System.out.print("nums[]: ");
                printArray(arr2);
                System.out.println("target: " + target);
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }

    public static void main3(String[] args) {
        int[] num = {0, 1, 1, 2, 4, 8, 10};
        System.out.println(binarySearchForFirstGreaterOrEqualNumIndex(num, 2));
        System.out.println(binarySearchForFirstLessOrEqualNumIndex(num, -1));
        System.out.println(binarySearchForFirstLessOrEqualNumIndex(num, 2));
        System.out.println(binarySearchForFirstGreaterNumIndex(num, 2));
        System.out.println(binarySearchForFirstGreaterNumIndex(num, 11));
    }

    public static void main2(String[] args) {
        int[] nums = {1, 2, 3, 4, 6, 7, 9, 10};
        System.out.println(binarySearchWithoutDuplicates(nums, 1));
        System.out.println(binarySearchWithoutDuplicates(nums, 10));
        System.out.println(binarySearchWithoutDuplicates(nums, 7));
        System.out.println(binarySearchWithoutDuplicates(nums, 8));
    }

    public static void main1(String[] args) {
        int testTime = 500000;
        int maxSize = 10;
        int maxValue = 10;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArrayWithoutDuplicates(maxSize, maxValue);
            Arrays.sort(arr1);
            int[] arr2 = copyArray(arr1);
            // random [0,1)
            // random * length [0,length)
            int target = arr1[(int) (Math.random() * arr1.length)];
            if (binarySearchWithoutDuplicates(arr1, target) != binarySearchComparator(arr2, target)) {
                succeed = false;
                System.out.print("nums[]: ");
                printArray(arr2);
                System.out.println("target: " + target);
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }
}
谢谢小天使请我吃糖果
0%