算法

006 二分搜索

在有序数组中查找特定元素是否存在、寻找大于等于某数的最左位置、小于等于某数的最右位置，以及在无序但相邻不相等的数组中寻找峰值（力扣162） 。

Posted by Hilda on March 7, 2025

算法系列：

003~005 二进制和位运算，三傻排序算法，对数器

1）在有序数组中确定num存在还是不存在

下面是我自己首先写的方法:

注：首先传入的数组一定是有序的（这是默认的条件）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public static boolean find_num(int[] arr, int num) {
    if (arr == null) return false;
    int right = arr.length -1 ;
    int left = 0;
    int mid;
    while (left <= right){
        mid = (left + right)/2;
        if (num == arr[mid]) {
            System.out.println("找到了在"+mid+"位置");
            return true;
        }
        if (num < arr[mid]) right = mid -1 ;
        if (num > arr[mid]) left = mid + 1;
    }
    return false;
}

同时我还写了一个对数器：(暴力法对比二分搜索法)

注：两个方法可能找到的位置不同，因为数组中可能会有相同的数字，另外要保证应用二分法或者暴力法的数组前提一定是有序的（我用了bubble排序）

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

import org.junit.Test;

import java.util.Arrays;

public class BinarySearch {

    //有序数组   确定num是否存在
    public static int find_num(int[] arr, int num) {
        if (arr == null) return -1;
        int right = arr.length -1 ;
        int left = 0;
        int mid;
        while (left <= right){
            mid = (left + right)/2;
            if (num == arr[mid]) {
                return mid;
            }
            if (num < arr[mid]) right = mid -1 ;
            if (num > arr[mid]) left = mid + 1;
        }
        return -1;
    }

    // 暴力法
    public static int find_with_traversal(int[] arr, int num){
        if (arr == null) return -1;
        for (int i = 0;i < arr.length;i++){
            if (arr[i] == num) return i;
        }
        return -1;
    }

    public static void main(String[] args)  {
        // 对数器
        int N = 1000;
        int len = 10;
        int v = 100;//数组中最大数的范围


        System.out.println("开始测试！");
        for (int i = 0;i < N;i++){
            int[] arr = produceSortedArray(len, v);
            // 确保数组是有序的
            bubble_sort(arr);
            int value;
            if (Math.random() < 0.5){
                // 随便指定一个数
                value = arr[(int)(Math.random()*arr.length)];//[0, arr.length-1]
            }else {
                value = v + 1;
            }
            // 注意：可能找到的位置，不同，但是是同一个数
            int index1 = find_with_traversal(arr,value);
            int index2 = find_num(arr, value);
            if (index2 != index1 && arr[index2] != arr[index1]){
                System.out.println("错误！"+ Arrays.toString(arr) + "找的是：" + value );
            }
        }
//        错误！[18, 30, 35, 48, 49, 49, 64, 86]找的是：49
//        错误！[19, 32, 35, 40, 40, 67, 70, 79, 98]找的是：40
//        错误！[19, 20, 34, 34, 57, 62, 82]找的是：34
//        错误！[25, 25, 31, 46, 60, 92, 95]找的是：25
//        错误！[15, 17, 23, 32, 32, 41, 66, 73, 75]找的是：32
//        错误！[6, 10, 20, 23, 23, 49, 61, 64, 97]找的是：23
//        错误！[7, 21, 46, 50, 60, 63, 63, 72, 97]找的是：63
//        int[] arr = {18, 30, 35, 48, 49, 49, 64, 86};
//        int value = 49;
//        System.out.println(find_with_traversal(arr, value));
//        System.out.println(find_num(arr, value));


        System.out.println("测试结束！");
    }

    public static int[] produceSortedArray(int len, int v){
        int len_arr = (int)(Math.random()*len) + 1;
        int[] arr = new int[len_arr];
        for (int i = 0;i < len_arr;i++){
            arr[i] = (int)(Math.random()*v)+1;
        }
        return arr;
    }

    // 冒泡排序
    public static void bubble_sort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++){
            int count = 1;//优化
            for (int j = 0;j < arr.length - i - 1;j++){
                if (arr[j] > arr[j+1]) {
                    swap(arr, j, j+1);
                    count += 1;
                }
            }
            if (count == 0) break;
        }
    }
    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

下面放左神的代码：(他给的是返回布尔值，我修改了下，返回索引，没找到返回-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public static int find_num(int[] arr, int num){
    if (arr == null || arr.length == 0){
        return -1;
    }
    int l = 0, r = arr.length - 1, m = 0;
    while(l <= r){
        m = l + ((r - l) >> 1); //技巧：用位运算代替除法
        if (arr[m] == num){
            return m;
        }else if(arr[m] > num){
            r = m - 1;
        }else {
            l = m + 1;
        }
    }
    return -1;
}

对数器可以仍旧用我上面写的。

2）在有序数组中找>=num的最左位置

根据上面这个对数器，很显然这个问题的情景是合理的。

这个算法的思想就是 ：

返回的位置记为ans，初始记为-1，然后二分，如果arr[m]>=num，那么记下答案（即ans=m）然后继续二分的思路；如果arr[m]<num，那么不记答案（不更新ans的值），继续二分。

代码就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public static int binaryMostLeft(int[] arr, int num){
    int ans = -1;
    if (arr == null || arr.length == 0) return ans;
    int l = 0;
    int r = arr.length - 1;
    while (l <= r){
        int m = l + ((r - l) >> 1);
        if (arr[m] >= num){
            ans = m;
            r = m - 1;
        }else {
            l = m + 1;
        }
    }
    return ans;
}

同理我也准备了对数器：

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

import java.util.Arrays;

public class Binary_Sort_Most_Left {

    // 找>=num的最左位置
    // 例如[3, 6, 9, 11, 11, 15]   num = 8  返回9所在的索引2
    public static int binaryMostLeft(int[] arr, int num){
        int ans = -1;
        if (arr == null || arr.length == 0) return ans;
        int l = 0;
        int r = arr.length - 1;
        while (l <= r){
            int m = l + ((r - l) >> 1);
            if (arr[m] >= num){
                ans = m;
                r = m - 1;
            }else {
                l = m + 1;
            }
        }
        return ans;
    }

    // 暴力法
    public static int mostLeftTraversal(int[] arr, int num){
        int ans = -1;
        for (int i = 0;i < arr.length;i++){
            if (arr[i] < num){
                ans = i;
            }else {
                return ans + 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
//        int[] arr = {3, 6, 9, 11, 11, 15};
//        System.out.println(MostLeftTraversal(arr, 8));
        // 对数器
        int N = 1000;// 次数
        int len = 100;
        int v = 100;
        System.out.println("开始测试");
        for (int i = 0;i < N;i++){
            int[] arr = produceArray(len, v);
            insert_sort(arr);
            int value = arr[(int)(Math.random()*len)];
            if (binaryMostLeft(arr, value) != mostLeftTraversal(arr, value)){
                System.out.println("出错了："+ Arrays.toString(arr));
            }
        }
        System.out.println("测试结束");

    }
    public static int[] produceArray(int len, int v){
        int[] arr = new int[len];
        for (int i = 0;i < len;i++){
            arr[i] = (int)(Math.random()*v)+1;//[1,v]整数
        }
        return arr;
    }

    //插入排序
    public static void insert_sort(int[] arr){
        // 0-1   1-2,  0- n-1
        for (int i = 1;i < arr.length;i++){
            int j = i;
            while(j > 0 && arr[j] < arr[j - 1]){
                swap(arr, j, j-1);
                j--;
            }
        }
    }
    public static void swap(int[] arr,int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

3）在有序数组中找<=num的最右位置

总结思路：

返回的位置记为ans，初始记为-1，然后二分，如果arr[m]<=num，那么记下答案（即ans=m）然后继续二分的思路；如果arr[m]>num，那么不记答案（不更新ans的值），继续二分。——>和上面“在有序数组中找>=num的最左位置”思路几乎差不多

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public static int binaryLessRight(int[] arr, int num) {
    int ans = -1;
    if (arr == null || arr.length == 0) return ans;
    int l = 0, r = arr.length - 1, m;
    while (l <= r) {
        m = l + ((r - l) >> 1);
        if (arr[m] <= num) {
            ans = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return ans;
}

我也写了对数器：

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

import java.util.Arrays;

public class Binary_Sort_Most_Right {
    // 在有序数组中找<=num的最右位置
    // [1, 1, 7, 9, 15, 29, 29]   num = 18  返回15所在的索引4
    public static int binaryLessRight(int[] arr, int num) {
        int ans = -1;
        if (arr == null || arr.length == 0) return ans;
        int l = 0, r = arr.length - 1, m;
        while (l <= r) {
            m = l + ((r - l) >> 1);
            if (arr[m] <= num) {
                ans = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return ans;
    }

    //暴力法
    public static int mostRight(int[] arr, int num) {
        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] <= num) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
//        int[] arr = {1, 1, 7, 9, 15, 29, 29};
//        System.out.println(binaryLessRight(arr, 18));

        //对数器
        int N = 1000; //次数
        int len = 1000;//数组长度
        int v = 100; // 值范围
        System.out.println("开始测试");
        for (int i = 0; i < N; i++) {
            int[] arr = produceArray(len, v);
            selectionSort(arr);// 保证是有序的
            int value = arr[(int)(Math.random()*len)];//[0,len-1]的整数
            if (mostRight(arr, value) != binaryLessRight(arr, value)){
                System.out.println("出错啦，arr="+ Arrays.toString(arr));
            }
        }
        System.out.println("结束测试");
    }

    public static int[] produceArray(int len, int v) {
        int[] arr = new int[len];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * v) + 1;
        }
        return arr;
    }

    //选择排序
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min_index = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[min_index] > arr[j]) min_index = j;
            }
            swap(arr, min_index, i);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

4）寻找峰值（力扣162）

二分搜索不一定发生在有序数组上（比如寻找峰值问题）

现在定义数组arr：任意相邻的数不相等，并且数组长度是N（第一个索引是0，最后一个索引是N-1），峰值是\(i\)位置当且仅当arr[i] > arr[i-1]且arr[i] > arr[i + 1]。那么两侧怎么办呢？假设有-1位置和N位置，两个位置都是无穷小。所以，0位置是峰值只需要arr[0] > arr[1]，N-1位置是峰值只需要arr[N - 1] > arr[N - 2]。

现在需要完成的任务是，在给定的数组满足上面条件的情况下，返回任意一个位置，只要其是峰值即可。（数组中显然存在1个或多个峰值，只需要返回一个即可）

如何解决？其实用二分也可以解决！！

为什么？可以听左神讲的！精准的空降链接

我把思路整理如下：

首先：观察0位置，如果arr[0] > arr[1]，那么找到了，直接返回0；如果arr[0] <= arr[1]，那么看N-1位置，arr[N-1] > arr[N - 2]，那么找到了，直接返回N-1。（这一步就是先看2侧）

如果上面不满足，那么在[1,N-2]范围上二分，为什么可以用二分解决呢？看下图：(把整个数组想象成一个波形，并且注意数组相邻的数不相等)

image-20250307103909347

所以通过在[1,N-2]范围上二分(m=1+((N-2-1)>>1))，寻找峰值。即判断arr[m]>arr[m-1]且arr[m]>arr[m+1]。

  • 如果arr[m]<=arr[m-1]，那么：

image-20250307104348132

  • 如果arr[m]>arr[m-1]但是arr[m]<=arr[m+1]，那么：

image-20250307104517720

  • 如果恰好arr[m]<=arr[m-1]且arr[m]<=arr[m+1]呢？如下图：

image-20250307104704008

那么随便挑一边进行二分即可！因为两半边都会有峰值存在！

所以：由于相邻元素不相等，数组不可能完全单调（全升或全降），否则与边界条件矛盾，因此一定能找到峰值。

每次二分时，无论 mid 的情况如何，排除的区间外一定保留至少一个峰值（由波形性质保证）。范围不断缩小，最终必然锁定一个峰值位置

用到的数学原理是很形象的，你管他叫中值定理，还是离散序列的极值定理等等都可以，反正画个图是个人都懂了。

综上对于峰值问题，其算法总结如下：

  • 先检查边界（0 和 N-1），若满足峰值条件直接返回。
  • 若边界无峰值，在 [1, N-2] 上二分：
    • 若 mid 是峰值，返回 mid。
  • 若 arr[mid] <= arr[mid-1]，左侧必有峰值，缩小到左侧。
  • 若 arr[mid] <= arr[mid+1]，右侧必有峰值，缩小到右侧。
  • 若 mid 是谷底，随意选一边即可。
  • 由于数组波形性质，二分必然找到一个峰值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public static int find_peak_index(int[] arr) {
    int N = arr.length;
    if (N == 1) return 0;// 题设就是-1位置和N位置是无穷小
    if (arr[0] > arr[1]) return 0;
    if (arr[N - 1] > arr[N - 2]) return N - 1;

    int l = 1, r = N - 2, m;
    while (l <= r) {
        m = l + ((r - l) >> 1);
        if (arr[m] > arr[m - 1] && arr[m] > arr[m + 1]) return m;
        if (arr[m] <= arr[m - 1]) {
            r = m - 1;
        }else {
            l = m + 1;
        }
    }
    return -1;
}

注：关于边界的考虑（比如数组是null，数组长度=0，数组长度只有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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

import java.util.Arrays;

public class FindPeak {

    // 返回峰值所在的位置
    public static int find_peak_index(int[] arr) {
        int N = arr.length;
        if (N == 1) return 0;// 题设就是-1位置和N位置是无穷小
        if (arr[0] > arr[1]) return 0;
        if (arr[N - 1] > arr[N - 2]) return N - 1;

        int l = 1, r = N - 2, m;
        while (l <= r) {
            m = l + ((r - l) >> 1);
            if (arr[m] > arr[m - 1] && arr[m] > arr[m + 1]) return m;
            if (arr[m] <= arr[m - 1]) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
//        int[] arr = {5, 6, 7, 5, 10, 7, 2, 1};
//        System.out.println(find_peak_index(arr));
        //对数器

        int N = 1000;//检测次数
        int len = 100;
        int v = 500;
        System.out.println("开始测试");
        for (int i = 0; i < N; i++){
            int[] arr = generateArray(len, v);
            int index = find_peak_index(arr);

            if (index == 0 && arr[0] < arr[1] ){
                System.out.println("出错了，index = 0");
                System.out.println("数组是"+Arrays.toString(arr));

            }else if (index == len - 1 && arr[len - 1] < arr[len - 2]){
                System.out.println("出错了，index = len - 1");
                System.out.println("数组是"+Arrays.toString(arr));
            }else if( index != 0 && index != len - 1 &&(arr[index] < arr[index - 1] || arr[index] < arr[index + 1])){
                System.out.println("出错了！！");
                System.out.println("index = " + index);
                System.out.println("arr[index] = " + arr[index]);
                System.out.println("arr[index - 1] = " + arr[index - 1]);
                System.out.println("arr[index + 1] = " + arr[index + 1]);
                System.out.println(Arrays.toString(arr));
            }
        }

        System.out.println("测试结束");



    }

    // 产生一个数字，任意相邻的数不相等
    // 长度为n(n >= 1), 每个元素值的范围是[1， v]
    public static int[] generateArray(int len, int v) {
        int[] arr = new int[len];
        arr[0] = (int) (Math.random() * v) + 1;

        if (len > 1) {
            for (int i = 1; i < len; i++) {
                int nextVal;
                do {
                    nextVal = (int) (Math.random() * v) + 1;
                } while (nextVal == arr[i - 1]);
                arr[i] = nextVal;
            }
        }
        return arr;

    }
}

二分搜索时间复杂度

如果数组长度为n，那么二分搜索搜索次数是log n次，以2为底

二分搜索时间复杂度\(O(log n)\)

CATALOG
    FEATURED TAGS
    书籍阅读 算法 人工智能AI基础 机器学习-吴恩达 力扣 Java基础 numpy ollama工具 pandas
    FRIENDS