文章

02 二分查找搜索

发表于 更新于
作者 Hacket Zeng
49 分钟阅读
02 二分查找搜索

二分查找/搜索基础

什么是二分查找？

二分查找是在有序表中查找目标元素的算法。不断的压缩范围数据的范围，最后当只剩下 1 个数据时答案已经被锁定了。

二分查找框架

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

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;
    while(...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

分析二分查找的一个技巧是：不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节。其中 … 标记的部分，就是可能出现细节问题的地方，当你见到一个二分查找的代码时，首先注意这几个地方。

二分搜索 mid 溢出: 如果 int mid = (left+right) /2 这样来计算 mid，可能出现 left 和 right 值过大，导致 mid 溢出了

1
2
3
4
5
6
7
8
9
10
11

int left = 1;
int right = Integer.MAX_VALUE; // 2147483647

int mid = (left + right) / 2; // left和right过大相加就溢出了
System.out.println("mid((left + right) / 2)=" + mid); // -1073741824

int mid1 = left + (right - left) / 2; // 推荐
System.out.println("mid1(left + (right - left) / 2)=" + mid1); // 1073741824

int mid4 = left + right >>> 1; // JDK 推荐，+运算符的优先级比>>>(无符号右移)高
System.out.println("mid4(left + right >>> 1)=" + mid4); // 1073741824

求中值引发的思考

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

int low = Integer.MAX_VALUE / 2;
int high = Integer.MAX_VALUE;

int mid = (low + high) / 2;
int mid2 = (low + high) >>> 1;
int mid3 = (low + high) >> 1;
int mid4 = low + (high - low) / 2;
int mid5 = low + ((high - low) >>> 1);
int mid6 = low + ((high - low) >> 1);
int mid7 = (low + high >>> 1); // 等同于low + high >>> 1 ， >>>比+号运算符优先级低

System.out.println("(low + high) / 2 = " + mid);
System.out.println("(low + high) >>> 1 = " + mid2);
System.out.println("(low + high) >> 1 = " + mid3);
System.out.println("low + (high - low) / 2 = " + mid4);
System.out.println("low + (high - low) >>> 1 = " + mid5);
System.out.println("low + (high - low) >> 1 = " + mid6);
System.out.println("low + high >>> 1 = " + mid7);

输出：

1
2
3
4
5
6
7

(low + high) / 2 = -536870913
(low + high) >>> 1 = 1610612735
(low + high) >> 1 = -536870913
low + (high - low) / 2 = 1610612735
low + (high - low) >>> 1 = 1610612735
low + (high - low) >> 1 = 1610612735
low + high >>> 1 = 1610612735

可以看到先进行 low+high 操作的，都溢出了，导致计算的结果不对

  1. >>> 比 + 号运算符优先级低
  2. 先进行 low+high 操作，会导致运算 Int 值溢出

二分查找分类

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

// 普通的二分查找
public static int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }
    return -1;
}
// 也可以是nums.length
public static int search1(int[] nums, int target) {
    int left = 0;
    int right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }
    // 防止target不存在时，left==right，会出现ArrayIndexOutOfBoundsException
    if (left == nums.length) return -1;
    // left<right循环终止条件是left==right，所以会少了left=right情况，需要判断下nums[left]==target的情况
    return nums[left] == target ? left : -1;
}
  1. 为什么 while 循环的条件中是 <=，而不是 <？

这是因为 right 的赋值是 nums.length-1，而不是 nums.length；前者相当于两端都闭区间 [left, right]，后者相当于左闭右开区间 [left, right)。

while(left<=right) 的终止条件是 left<=right+1 写成区间形式就是 [right+1, right]

while(left<right) 的终止条件是 left==right，写成区间形式就是 [right, right]，这个时候会有一个 left 值被漏掉了

如果是 while(left<=right), right=nums.length, int[] nums = {-1, 0, 3, 5, 9, 12}; target=13，这种情况出出现 ArrayIndexOutOfBoundsException

  1. 为什么 left = mid + 1，right = mid - 1？我看有的代码是 right = mid 或者 left = mid，没有这些加加减减

刚才明确了「搜索区间」这个概念，而且本算法的搜索区间是两端都闭的，即 [left, right]。那么当我们发现索引 mid 不是要找的 target 时，下一步应该去搜索哪里呢？

当然是去搜索区间 [left, mid-1] 或者区间 [mid+1, right] 对不对？因为 mid 已经搜索过，应该从搜索区间中去除。

  1. 算法的缺陷

有序数组 nums = [1,2,2,2,3]，target 为 2，此算法返回的索引是 2，如果想得到 target 的左边界，该算法是无法处理的。

2、寻找等于 target 最左侧值的索引

  1. 初始时 left=0, right=nums.length-1，while 循环条件为 left<=right
  2. 每次循环比较 mid 值和 target
    1. mid 值小于 target，说明 target 在 mid 右侧，那么缩小左边范围 left=mid+1
    2. mid 值大于 target，说明 target 在 mid 左侧，那么缩小右边范围 right=mid-1
    3. mid 值等于 target，由于我们是要寻找最左边的 target 的值，所以还需要向左边靠拢缩小右边的范围 right=mid-1
  3. 处理好边界问题
    1. 如果 target 不是数组中的值，且大于数组中最右侧的值，那么在循环结束后，left=nums.length, 需要判断 left 是否超出了 nums.length，超出了就返回 -1
    2. 如果 target 不是数组中的值且小于数组中的最左侧的值或者 target 为数组中第 0 个位置元素，那么在循环结束后，left=0，需要判断 nums[left] 是否等于 target，来决定返回 left 还是返回 -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 searchLeftBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) { // // 搜索区间为 [left, right] 终止条件是，left>right, left=0,right=-1或left=nums.length,right=nums.length-1
        int mid = left + right >>> 1;
        if (nums[mid] == target) {
            // 搜索区间变为 [left, mid-1] mid在target右边，不断缩小右边边界
            right = mid - 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right] mid在target的左边
            left = mid + 1;
        }
    }
    // 循环结束条件1 left=right=0，判断left是否等于target，还是大于target
    // 循环结束条件2 left=right=nums.length-1，target不存在，left=right+1=nums.length
    
    // target为大于最右侧元素不存在的元素，导致不停地往右侧收缩
    if (left == nums.length) return -1;
    // target为第0号元素时，left=right=0，需要最后判断一下nums[left]是不是target，否则出现不是target也返回了0
    return nums[left] == target ? left : -1;
}

3、寻找等于 target 最右侧值的索引

思路

  1. 和普通的二分搜索思路一致
  2. 不同的是
    1. mid 处值等于 target 值，由于我们是要寻找最右侧的值，所以需要向右靠拢，那就需要不断缩小左边的值，即 left=mid+1（这个时候 left 可能最后会等于 nums.length）
    2. 最后返回的是 left-1，因为最后一次的 left 加了 1
    3. 如果 target 为左侧不存在的值，此时 left=0，可能会越界，需要判断下 left-1 小于 0 时直接返回 -1
    4. 如果 target 为右侧不存在的值或者为最右的值，都是 left=nums.length，需要判断是否等于 target 就返回 left-1，否则返回 -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 searchRightBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) { // 小于target需要不停地往右靠拢
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) { // 大于target
            right = mid - 1;
        }
    }
    // 循环结束条件1：left=right=0，target小于等于最左边的值，left=1，right=0
    // 循环结束条件2：left=right=nums.length-1，不管的等于还是小于target，left=nums.length，right=nums.length-1，需要判断下left是否等于target

    // 如果target小于数组左侧最小值（不在数组中存在），left=0, right=-1，越界
    if (left - 1 < 0) return -1;
    // target为右侧一个不存在的元素，left=right=nums.length-1， 因为left=mid+1，最多一趟多加了1，返回时要减去1
    return nums[left - 1] == target ? left - 1 : -1;
}

4、寻找最接近 target 的最左边值的索引

思路

  1. 寻找等于 target 最左侧值的索引不同，当 target 不存在于数组时，不返回 -1，而是返回离它最近的索引
  2. 就不需要判断该元素是否存在于第 0 一个索引还是该元素不存在数组且小于最左边的值，都是返回 left
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// 二分搜索变种 寻找最接近target的最右边值的索引，不存在返回最近的索引
public static int searchLeftNearest(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + right >>> 1;
        if (nums[mid] == target) {
            // 向左靠拢，缩小right
            right = mid - 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }
    // 如果存在target大于数组中最右侧值，left=nums.length，可能越界
    if (left >= nums.length) {
        left = nums.length - 1;
    }
    return left;
}

5、寻找最接近 target 的最右边值的索引

思路

  1. 寻找等于 target 最左侧值的索引不同，当 target 不存在于数组时，不返回 -1，而是返回离它最近的索引
  2. 就不需要判断该元素是否存在于最后一个索引还是该元素不存在且大于数组最右侧的值，都是返回 left-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 二分搜索变种 返回离target最近的最右边的索引，不存在返回最近的索引
public static int searchRightNearest(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + right >>> 1;
        if (nums[mid] == target) {
            // 向右靠拢，缩小left
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }
    // 判断下target为最左侧不存在的值，left=0时
    int val = left - 1;
    if (val < 0) {
        val = 0;
    }
    return val;
}

二分搜索边界处理技巧

1. while 用小于等于还是小于

  • while(left<=right)，搜索区间为 [left,right]
  • while(left<right)，搜索区间为 [left,right)

判断是否需要 left==right 的条件判断，如果需要，用 left<=right，不需要就用 left<right

2. 用 right=mid 还是 right=mid+1

  • 如果搜索区间为 [left, right] 左闭右闭，用 right=mid+1
  • 如果搜索区间为 [left, right) 左闭右开，用 right=mid；所以当 nums[mid] 被检测之后，下一步应该去 mid 的左侧或者右侧区间搜索，即 [left, mid) 或 [mid + 1, right)。

二分查找相关题

69. x 的平方根

题目：

给你一个非负整数 x ，计算并返回 x 的 算术平方根。 由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。 输入：x = 4 输出：2 输入：x = 8 输出：2

解法 1：二分法

思路：

  1. 其实这是一个查找整数的问题：
    1. 这个数的平方等于 x，那么就找到了这个整数
    2. 这个数的平方大于 x，那么这个整数肯定不是要找的数，因为大于了，我们要找的是等于或小于这个数的（等于的就是刚好平方=x，小于的是最接近该数的舍去小数点）
    3. 这个数的平方小于 x，那么这个数可能是我们要找的数
  2. 因此我们可以使用二分查找来查找这个整数，不断缩小范围；start=0, end=x, 一个 res 记录结果值，每次 mid 的平方和 x 进行比较（判断时注意乘法溢出）：
    1. mid 平方等于 x 时（恰好是），res=mid，直接返回 res
    2. mid 平方大于 x 时（大了往小猜），说明目标值在 mid 的左边，mid-1，由于大了不可能是目标值，所以不需要用 res 记录
    3. mid 平方小于 x 时（小了可能是也可能不是），说明目标值在 mid 的右边，记录当前 res=mid，mid+1（res 记录当前 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

public int mySqrt(int x) {
    int start = 0;
    int end = x;
    int res = -1; // 记录结果值
    while (start <= end) { // 不是<，要<=，只有一个值的话<不能满足
        int mid = start + (end - start) / 2;
        long temp = (long) mid * mid; // 注意转成long，否则int溢出
        if (temp <= x) {
            res = mid; // 记录最接近x的值，如果下一趟大于x了，res就是最接近的
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return res;
	}
}
// 用除法替代乘法，防止溢出
public int mySqrt(int x) {
    // 特殊值判断
    if (x == 0 || x == 1) {
        return x;
    }
    int start = 0;
    int end = x;
    int res = -1; // 记录结果值
    while (start <= end) { // 不是<，要<=
        int mid = start + (end - start) / 2;
        // 防止溢出，用除法
        if (mid == x / mid) {
            return mid;
        } else if (mid > x / mid) {
            end = mid - 1;
        } else {
            res = mid; // 记录最接近x的值，如果下一趟大于x了，res就是最接近的
            start = mid + 1;
        }
    }
    return res;
}

解法 2：二分优化版

  1. 用除法替代乘法，防止乘法溢出
  2. 一个整数的平方根肯定不会超过它自己的一半，但是 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

public int mySqrt(int x) {
    // 特殊值判断
    if (x == 0 || x == 1) {
        return x;
    }
    // 目标值不会大于x/2，所以end的值直接从x/2开始
    int start = 1;
    int end = x / 2;
    int ans = 0;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (mid == x / mid) {
            ans = mid;
            break;
        } else if (mid > x / mid) {
            end = mid - 1;
        } else {
            ans = mid;
            start = mid + 1;
        }
    }
    return ans;
}

704. 二分查找 easy

题目

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

解法 1：最基本的二分搜索

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

public static int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }
    return -1;
}

解法 2：JDK 的二分搜索 最优解

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

public int search(int[] nums, int target) {
    int low = 0;
    int high = nums.length - 1;
    while (low <= high) {
        int mid = low + high >>> 1;
        int midVal = nums[mid];
        if (midVal < target) {
            low = mid + 1;
        } else {
            if (midVal == target) {
                return mid;
            }
            high = mid - 1;
        }
    }
    return -1;
}

剑指 Offer 53 - I. 在排序数组中查找数字 I

题目

统计一个数字在排序数组中出现的次数。

解法 1：二分搜索，先搜索 left，再搜索 right，最后 right-left+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

public static int search(int[] nums, int target) {
    if (nums == null || nums.length == 0) return 0;
    int leftIndex = searchLeft(nums, target);
    int rightIndex = searchRight(nums, target);
    if (leftIndex == -1 || rightIndex == -1) {
        return 0;
    }
    return rightIndex - leftIndex + 1;
}

private static int searchLeft(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + right >>> 1;
        if (nums[mid] == target) {
            // 向左靠拢，缩小right
            right = mid - 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }
    // 如果target不存在数组且target小于数组最左侧元素，更改的是right，与left无关
    // 如果target不存在数组且target大于数组最右侧元素，此时left=nums.length
    if (left >= nums.length) {
        return -1;
    }
    // 如果target在最后一个元素或者大于最右一个元素
    return nums[left] == target ? left : -1;
}

private static int searchRight(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + right >>> 1;
        if (nums[mid] == target) {
            // 向右靠拢，缩小left
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }
    // left=mid+1，最后返回的要-1
    // 如果target不存在数组且target小于数组最左侧元素，此时left=0，right=-1
    if (left - 1 < 0) {
        return -1;
    }
    // 如果target不存在数组且target大于数组最右侧元素，此时更换的是left，所以返回时left要-1
    // 如果target为最后一个元素或target不在数组且大于数组最后一个元素
    return nums[left - 1] == target ? left - 1 : -1;
}

旋转排序数组

33,34,81,153,154,162 题

  • 33- 查找旋转数组不重复；
  • 81- 查找旋转数组可重复复；
  • 153- 旋转数组最小值不重复；
  • 154 旋转数字最小值重复

都是旋转数组的题，区别是题目的条件限制不一样。旋转数组是这样的一种数组：将一个按升序排列好的数组，往右侧循环移位，使得整个数组形成左右两个有序区间，且左区间的数都比右区间的数大。比如 [5,6,7,8,1,2,3,4]。

153 和 33 这两道题给定的条件都是，数组中的元素互不相同。153 是找最小值，33 是找给定值。

54 和 81 这两道题给定的条件都是，数组中的元素可能重复。154 是找最小值，81 是找给定值。

解题思路都是二分，找最小值比找给定值要简单一些。https://blog.csdn.net/vcj1009784814/article/details/124702379

33. 搜索旋转排序数组 medium (无重复值找 target)

题目

整数数组 nums 按升序排列，数组中的值 互不相同 。 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， ` [0,1,2,4,5,6,7] ` 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。 输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4 输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1

思路

  • 时间复杂度为 O(log n)，第一时间想到的就是二分搜索法，而二分法的前提条件是有序，而题目中旋转后整体变成了无序，就没法用二分法了；仔细观察旋转后的数组是有一边是有序，所以我们只需要找到这部分有序的应用二分法，重点是找到有序的数组：比较 mid 处的值和 start 处的值或者 mid 和 end 的值
  • 取 mid 处的值和 start 处的值比较（mid 和 end 也可以）
    • 如果 mid>=start 处值，代表前 _ 半部分有序 _（如 4567123）；需要等于号，需要考虑只有一个元素且是 target 的情况下
      • 比较 mid 和 target 相等？相等那么 mid 就是要找的索引
      • 如果 target 值在 [start,mid] 前半部分有序之间（包括等于），那么对这部分进行二分查找，往前搜索，即 end=mid+1（为什么是 mid+1?因为前面已经用 mid 和 target 进行了比较是否相等了）
      • 如果 target 不在 [start,end] 之间，那么需要 start=mid+1，即 target 可能在 [mid+1,end] 之间；那么此时 [mid+1, end] 算一个新的数组，继续循环上面的逻辑
    • 如果 mid<start 处值，代表后半部分有序
      • 如果 target 在后半部分，即 target 在 [mid, end]，那么 start=mid+1，继续二分搜索
      • 如果 target 在前半部分，那么 end=mid-1；继续循环上面的逻辑
  • 循环结束条件是 start<=end，需要等于是需要考虑只有 2 个元素且 target 是其他的一个的情况
  • 这个二分搜索里面的逻辑判断都是需要等于的，主要是需要判断只有 1 个元素和 2 个元素的情况

题解

代码 1：mid 和 start 比较

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

public static int search(int[] nums, int target) {
    int n = nums.length;
    // 边界判断，一个元素的情况
    if (nums.length == 1) {
        return nums[0] == target ? 0 : -1;
    }
    int start = 0;
    int end = n - 1;
    while (start <= end) { //
        int mid = start + (end - start) / 2;
        // 如果相等return
        if (nums[mid] == target) {
            return mid;
        }
        // 这一步的作用就是找到有序的区间：由于前面比较了mid和target，故缩小有序区间时，直接+-1即可
        if (nums[mid] >= nums[start]) { // 前半部分有序；为什么是>=，要加等于是因为只有一个元素的情况下且等于target要考虑
            if (nums[start] <= target && target <= nums[mid]) { // 在前半部分，往前找
                end = mid - 1;
            } else { // 在后半部分，可能无序
                start = mid + 1;
            }
        } else { // 后半部分有序
            if (nums[mid] <= target && target <= nums[end]) { // 在后半部分有序，往后找
                start = mid + 1;
            } else { // 在前半部分，可能无序
                end = mid - 1;
            }
        }
    }
    return -1;
}

代码 2： mid 和 end 比较

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

public static int search(int[] nums, int target) {
    int n = nums.length;
    // 边界判断，一个元素的情况
    if (nums.length == 1) {
        return nums[0] == target ? 0 : -1;
    }
    int start = 0;
    int end = n - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;

        if (nums[mid] == target) {
            return mid;
        }
        // mid和end比
        if (nums[mid] <= nums[end]) { // 右边有序
            if (nums[mid] <= target && target <= nums[end]) {
                // 在右边有序区间内，往后移动，由于前面已经判断了mid是否等于target，所以mid+1
                start = mid + 1;
            } else { // 在左边
                end = mid - 1;
            }
        } else { // 左边有序
            if (nums[start] <= target && target <= nums[mid]) {
                // 在左边有序区间内，往前走
                end = mid - 1;
            } else { // 在右边无序区间内
                start = mid + 1;
            }
        }
    }
    return -1;
}

34. 在排序数组中查找元素的第一个和最后一个位置 medium

题目

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

解法 1：先找到 target 的左边界，再找到 target 的右边界

思路

  1. 题目写的是递增有序数组，且要求 O(log n) 时间复杂度，那么可以想到二分搜索法
  2. 先找到等于 target 的最左边的索引
  3. 再找到等于 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
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

public static int[] searchRange(int[] nums, int target) {
    if (nums == null || nums.length == 0) return new int[]{-1, -1};
    int left = searchLeft(nums, target);
    int right = searchRight(nums, target);
    return new int[]{left, right};
}

// 搜索值为target的最左边的索引
private static int searchLeft(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + right >>> 1;
        if (nums[mid] == target) { // 等于需要不断向左靠拢
            right = mid - 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }
    // 循环结束条件1 left=right=0，不管是等于还是大于target，left=0，right=-1，判断left是否等于target，还是大于target
    // 循环结束条件2 left=right=nums.length-1，target不存在，left=right+1=nums.length

    // target在右侧不存在的值，left可能等于nums.length
    if (left == nums.length) return -1;
    // 返回left
    return nums[left] == target ? left : -1;
}

private static int searchRight(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + right >>> 1;
        if (nums[mid] == target) {
            // 找右边，需要向右靠拢，需要不断缩小左区间
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    // 循环结束条件1：left=right=0，target小于等于最左边的值，left=1，right=0
    // 循环结束条件2：left=right=nums.length-1，不管的等于还是小于target，left=nums.length，right=nums.length-1，需要判断下left是否等于target

    // 如果target小于数组左侧最小值，left=0, right=-1
    if (left - 1 < 0) return -1;
    // 最后返回left-1
    return nums[left - 1] == target ? left - 1 : -1;
}

复杂度

  • 时间复杂度： O(logn) ，其中 n 为数组的长度。二分查找的时间复杂度为 O(logn)，一共会执行两次，因此总时间复杂度为 O(log n)。
  • 空间复杂度：O(1) 。只需要常数空间存放若干变量。

81. 搜索旋转排序数组 II medium (有重复值找 target)

题目：

和 33 题类似，只是元素可能有重复 输入：nums = [2,5,6,0,0,1,2], target = 0 输出：true 输入：nums = [2,5,6,0,0,1,2], target = 3 输出：false

思路：

  • 和 33 题类似，就是有重复值，当 mid 和 start 有重复值时，我们是不知道哪边是有序的数组的
    • 10111 和 1110111101 这种。此种情况下 nums[start] == nums[mid]，分不清到底是前面有序还是后面有序，此时 start++ 即可。相当于去掉一个重复的干扰项。
    • 直到 start 和 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

public static boolean search(int[] nums, int target) {
    // 边界
    int n = nums.length;
    if (n == 1) {
        return nums[0] == target;
    }
    int start = 0;
    int end = n - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;

        if (nums[mid] == target) {
            return true;
        }
        // 相同了，start往前走，直到不相等
        if (nums[start] == nums[mid]) {
            start++;
            continue;
        }
        if (nums[mid] > nums[start]) { // 前半段有序
            // 前半段有序，且target在前半段
            if (nums[start] <= target && target < nums[mid]) { // 需要start<=target，否则nums={1, 2, 2, 2},target=1会不通过
                end = mid - 1;
            } else { // 在后半段无序
                start = mid + 1;
            }
        } else { // 后半段有序
            // 在后半段有序区间
            if (nums[mid] < target && target <= nums[end]) {
                start = mid + 1;
            } else { // 在前半段无序区间
                end = mid - 1;
            }
        }
    }
    return false;
}

153. 寻找旋转排序数组中的最小值（无重复值找最小值） medium

题目（返回有序数组经过 n 次旋转后的最小值）

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到： 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2] 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7] 注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。 输入： nums = [3,4,5,1,2] 输出： 1 解释： 原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

解法 1：二分搜索

思路

  1. 题目是有序，且要求时间复杂度为 O(log n)，那么可以想到用二分查找法；用二分法查找，需要始终将目标值（这里是最小值）套住，并不断收缩左边界或右边界。
  2. 左、中、右三个位置的值相比较，有以下几种情况：

jcsoz

  1. 通过判断中和右边值的大小，来确定最小值在哪边，从而确定怎么缩小范围
    1. 如果中值 < 右值，则最小值在左半边，可以收缩右边界。
    2. 如果中值 > 右值，则最小值在右半边，可以收缩左边界。
  2. 最后返回 left（返回 right 也可以）

疑惑？

  1. 循环条件为什么是 left<right，而不是 left<=right

相邻的元素比较就可以了，相同的元素不需要比较了

  1. left=mid+1,right=mid，为啥不能是 right=mid+1
  • 中>右，最小值在右半边，中肯定不是最小值，收缩左边，left 可以跨过 mid，所以 left=mid+1；
  • 中<右，最小值在左半边，中值也可能是最小值，收缩右边，right 不可跨过 mid，所以 right=mid
  1. 为啥返回 left，不能返回 right 吗？

都可以的

  1. 为啥是 mid 和 right 比，不能和 left 比？

简单讲就是因为我们找最小值，要偏向左找，目标值右边的情况会比较简单，容易区分，所以比较 mid 与 right 而不比较 mid 与 left 能，转换思路，不直接找最小值，而是先找最大值，最大值偏右，可以通过比较 mid 与 left 来找到最大值，最大值向右移动一位就是最小值了（需要考虑最大值在最右边的情况，右移一位后对数组长度取余）

题解
二分查找：为什么左右不对称？只比较mid与right的原因

  • 找最小值：mid 和 right 比；也可和 left 比，找到最大值，下一个就是最小值
  • 找最大值，mid 和 left 比，

代码

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

public int findMin(int[] nums) {
    int left = 0;
    int right = nums.length - 1;                /* 左闭右闭区间，如果用右开区间则不方便判断右值 */ 
    while (left < right) {                      /* 循环不变式，如果left == right，则循环结束 */
        int mid = left + (right - left) / 2;    /* 地板除，mid更靠近left */
        if (nums[mid] > nums[right]) {          /* 中值 > 右值，最小值在右半边，收缩左边界 */ 
            left = mid + 1;                     /* 因为中值 > 右值，中值肯定不是最小值，左边界可以跨过mid */ 
        } else if (nums[mid] < nums[right]) {   /* 明确中值 < 右值，最小值在左半边，收缩右边界 */ 
            right = mid;                        /* 因为中值 < 右值，中值也可能是最小值，右边界只能取到mid处 */ 
        }
    }
    return nums[left];    /* 循环结束，left == right，最小值输出nums[left]或nums[right]均可 */     
}

复杂度

  • 时间复杂度为：O(log n)
  • 空间复杂度为：O(1)

154. 寻找旋转排序数组中的最小值2(有重复值) hard

思路

  1. 和 153 题无重复值的思路大体一致，主要区别是要处理等于的情况
  2. 当 mid 和 right 相等时，由于 mid 和 right 相等了，无法确定最小值所在，只能通过不断缩小右边来确定 [11122222] [33322222]

代码

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

public static int findMin(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) { // 两个相邻的元素就可以比较了，不需要处理left=right，循环结束条件是left=right
        int mid = left + right >>> 1;
        if (nums[mid] > nums[right]) {
            // 1、mid>right，说明最小值在右边，缩小左边
            left = mid + 1; // mid不可能是最小值，left可以跳过mid，可加1
        } else if (nums[mid] < nums[right]) {
            // 2、mid<right，说明最小值在左边，缩小右边，mid可能为最小值，mid不可跳过
            right = mid;
        } else if (nums[mid] == nums[right]) {
            // 3、mid==right，暂时无法确定，由于mid到right都是相同的值，所以得往左靠拢，缩小右边才能确定  [11122222] [33322222]
            right--;
        }
    }
    return nums[left];
}

局部最小值问题

二维数组中的查找

  1. 逐层二分查找
  2. 利用数组递增特性线性搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public boolean Find3(int target, int[][] array) {
    // 如果当前数字比target大
    for (int i = array.length - 1; i >= 0; i--) {
        int[] arr = array[i];
        for (int j = 0; j < arr.length; j++) {
            int val = arr[j];
            if (val < target) { // 继续往右遍历
                System.out.println("当前val(" + val + ")小于target(" + target + ") 继续往右遍历i=" + i + ",j=" + j);
            } else if (val > target) { // 往上遍历，结束当前轮遍历
                System.out.println("当前val(" + val + ")小于target(" + target + ") 结束该层遍历i=" + i + ",j=" + j);
                break;
            } else {
                System.out.println("找到了，[" + i + "][" + j + "]");
                return true;
            }
        }
    }
    return false;
}

查找数组顶峰

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

/**
 * 需要找到一个比两边都大的元素
 */
public int findPeakElement(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int mid = left + right >>> 1;
        System.out.println("left=" + left + ",right=" + right + ",mid=" + mid);
        if (nums[mid] > nums[mid + 1]) { // 下坡，峰值在左边
            right = mid;
        } else { // 上坡，峰值在右边
            left = mid + 1;
        }
    }
    return right;
}
数据结构和算法, 基础
数据结构和算法
本文由作者按照 CC BY 4.0 进行授权