二分查找-合集总结

字数统计: 9.9k字   |   阅读时长≈ 40分钟

二分查找-合集总结

（本系列是针对Leetcode上常见的二分查找题目进行总结。）

总体思想：把待搜索的目标值留在最后判断，在循环体内不断地把不符合题目要求的子区间排除掉，在退出循环以后，因为只剩下 1 个数没有看到，它要么是目标元素，要么不是目标元素，单独判断即可。

用这种思路写二分不容易出错，需要考虑的细节最少。

  • 这种思路也非常符合“二分”这个名字，就是把【待搜索的区间】分为【有目标元素的区间】和【不包含目标元素的区间】，排除掉【不包含目标元素的区间】，剩下的就是有【目标元素的区间】。
  • 初学写二分查找的问题是：跳步厉害，写下 left = mid 或者 right = mid - 1 等代码的时候，一定要搞清楚是什么意思，必要的时候写上注释，帮助自己思考和以后复查代码。
  • 算法问题建议更多地理解思想，思考为什么这样写，而不建议背代码，背模板。即使要用代码和模板，例如并查集、线段树这种，也应该先把它们保存到自己的 github 代码仓库里，要用的时候去复制粘贴。

PS：分类是liweiwei老哥总结好的，在他的分类下，下文将以自己的思想将题目串通总结起来。

二分总结链接：https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/

1. 题目分类

「力扣」上的二分查找问题主要有这三类题型。

一、在数组中查找符合条件的元素的索引

一般而言这个数组是有序的，也可能是半有序的，但不大可能是无序的。

题目 提示与题解
704. 二分查找 二分查找的模板问题，使用本题解介绍的方法就要注意，需要“后处理”。
34. 在排序数组中查找元素的第一个和最后一个位置 查找边界问题，题解（有视频讲解）。
33. 搜索旋转排序数组 题解
81. 搜索旋转排序数组 II 题解
153. 寻找旋转排序数组中的最小值 题解
154. 寻找旋转排序数组中的最小值 II 题解
300. 最长上升子序列 二分查找的思路需要理解，代码很像第 35 题，题解。
275. H指数 II 题解
1095. 山脉数组中查找目标值 题解
852. 山脉数组的峰顶索引（简单）
658. 找到 K 个最接近的元素（中等） 题解，这个问题二分的写法需要做复杂的分类讨论，可以放在以后做。
4. 寻找两个有序数组的中位数 官方题解（有视频讲解），题解

二、在一个有上下界的区间里搜索一个整数

题目 提示与题解
69. 平方根 在一个整数范围里查找一个整数，也是二分查找法的应用场景，题解。
287. 寻找重复数 题解。在一个整数范围里查找一个整数。
374. 猜数字大小 题解
1300. 转变数组后最接近目标值的数组和 题解

三. 判别条件是一个函数

题目 提示与题解
278. 第一个错误的版本
410. 分割数组的最大值 经典问题，判别函数的写法很有技巧，题解。
658. 找到 K 个最接近的元素 题解
875. 爱吃香蕉的珂珂 题解
1300. 转变数组后最接近目标值的数组和 题解

2. 分类1：在数组中查找符合条件的元素的索引

题目1：704. 二分查找

1. 题目描述：

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

1
2
3
4
5
6
7
8
9
10
11
示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。

2.算法思路

  • 经典的二分查找法（暂时不在这里详细叙述，各位有算法基础的大佬应该闭着眼睛都能写）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int search(int[] nums, int target) {
        int left  = 0;
        int right = nums.length - 1;

        while (left <= right){
            int mid = (left + right) >>> 1;

            if (nums[mid] == target){
                return mid;
            }else if (nums[mid] < target){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

复杂度分析

  • 时间复杂度：O(logN) < O(N)
  • 空间复杂度：O(1)

上述的做法实际上是将待搜索的区间分为了三个区间

mark

这种写法的弊端是：返回的边界问题（读者可以想一想弊端具体发生的情况）

mark

接下来提供另外一种：二分查找的思想（排除法）

  • mid被分到左边区间
  • mid被分到右边区间

mark

mark

死循环可能产生的原因：

mark

题目2：35. 搜索插入位置

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
class Solution {
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;

        if (len == 0){
            return 0;
        }

        // 特判
        if (nums[len - 1] < target){
            return len;
        }

        int left  = 0;
        int right = nums.length - 1;

        while (left < right){
            int mid = (left + right) >>> 1;
            // 什么时候不是解
            // 如果严格小于不是解
            if (nums[mid] < target){
                // 下一轮搜索的区间是[mid + 1,right]
                left = mid + 1;
            }else {
                // 相反的区间[left,mid]
                right = mid;
            }
        }
        return left;
    }
}

复杂度分析：

  • 时间复杂度：O(logN)，这里 N 是数组的长度，每一次都将问题的规模缩减为原来的一半，因此时间复杂度是对数级别的；
  • 空间复杂度：O(1)。

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

题目描述：

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

1
2
3
4
5
6
7
8
9
示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

算法思想

  • nums[mid] < target 一定不是开始位置的解
  • 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
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
class Solution {
    public int[] searchRange(int[] nums, int target) {

        int len = nums.length;
        // 特判
        if (len == 0){
            return new int[]{-1,-1};
        }

        // 开始位置
        int firstPosition = findFirstPosition(nums,target);

        // 如果开始位置都没找到这个元素
        if (firstPosition == -1){
            return new int[]{-1,-1};
        }

        // 结束位置
        int lastPosition = findLastPosition(nums,target);

        return new int[]{firstPosition,lastPosition};
    }

    private int findFirstPosition(int[] nums, int target) {
        int left  = 0;
        int right = nums.length - 1;

        while (left < right){
            // 下取整
            int mid = (left + right) >>> 1;

            // 什么时候不是解
            // 严格小于不是解
            if (nums[mid] < target){
                // 下一轮 搜索区间[mid + 1,right]
                left = mid + 1;
            }else {
                // nums[mid] >= target
                // 搜索区间是[left,mid]
                right = mid;
            }
        }
        // 对查找的数进行判断
        if (nums[left] == target){
            return left;
        }
        return -1;
    }


    // 这时候如果向下取整会有死循环的产生
    private int findLastPosition(int[] nums, int target) {
        int left  = 0;
        int right = nums.length - 1;

        while (left < right){
            // 上取整
            int mid = (left + right + 1) >>> 1;

            // 大于一定不是解
            if (nums[mid] > target){
                // 下一轮搜索的区间是[left,mid - 1]
                right = mid - 1;
            }else {
                // 下一轮搜索的区间是[mid,right]
                left = mid;
            }
        }
        return left;
    }
}

复杂度分析：

  • 时间复杂度：O(log N)，这里 N 是数组的长度，两个子问题都是二分查找，因此时间复杂度为对数级别。
  • 空间复杂度：O(1)，只使用了常数个数的辅助变量、指针。

题目4：33. 搜索旋转排序数组

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

1
2
3
4
5
6
7
8
9
10
示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
    
    
示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -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
// 二分法
// 讨论中间元素和有边界的关系
class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length;

        // 特判
        if (len == 0){
            return -1;
        }


        int left  = 0;
        int right = nums.length - 1;

        while (left < right){
            int mid = (left + right + 1) >>> 1;

            if (nums[mid] < nums[right]){
                // 使用上取整的中间数，必须在上面的 mid 表达式的括号里 + 1
                if (nums[mid] <= target && target <= nums[right]){
                    // 下一轮搜索区间是[mid,right]
                    left = mid;
                }else {
                    // 只要上面对了，这个区间是上面区间的反面区间，下一轮搜索区间是 [left, mid - 1]
                    right = mid - 1;
                }
            }else { // nums[mid] >= nums[right]
                // [left, mid] 有序，但是为了和上一个 if 有同样的收缩行为，
                // 故意强行认为[left, mid - 1]有序
                // 当区间只剩下2个元素的时候 int mid = (left + right + 1) >>> 1 ;一定会取到右边
                // 此时mid - 1不会越界
                if (nums[left] <= target && target <= nums[mid - 1]){
                    right = mid - 1;
                }else {
                    // 下一轮搜索区间是[mid,right]
                    left = mid;
                }
            }
        }
        // 有可能不存在目标元素，因此还需要做一次判断
        if (nums[left] == target){
            return left;
        }
        return  -1;
    }
}

题目 5 ： 153. 寻找旋转排序数组中的最小值

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

1
2
输入: [3,4,5,1,2]
输出: 1

示例 2:

1
2
输入: [4,5,6,7,0,1,2]
输出: 0

思路

  • 旋转排序数组，几乎都是有序的数组，也可以通过比较特定位置的元素判断达到”减治“的效果（逐渐缩小区间）
  • 很自然地，我们会看中间数（位于待搜索区间中间位置的元素，由于不是有序数组，因此不能称之为中位数）。

这时候有两个思路：

  • 思路一：看看搜索区间左边界和 ”中间数“（注意这里不是中位数），是不是可以缩小搜索区间的范围；
  • 思路 2：看看当前搜索区间的右边界和“中间数”（注意这里不是中位数），是不是可以缩小搜索区间的范围；

要想清楚这个问题，我们不妨举几个例子。

针对思路1：

例 1：[1, 2, 3, 4, 5]

例 2：[2, 3, 4, 5, 1]

  • 这两个例子中 ”中间数“都比左边界大，但是旋转排序数组的最小值一个在中间数的左边，一个在中间数的右边，因此思路1是不可行的。

针对思路2

例 3：[7, 8, 9, 10, 11, 12, 1, 2, 3]

例 4：[7, 8, 1, 2, 3]

  • 中间数 11 比 3 大，因此中间数左边的数字都不可能是旋转排序数组的最小值，因此下一轮搜索的区间是 [mid + 1,right]
  • 再看例4 ， 中间数到右边界是递增的， 1 比 3 小，那么中间数右边的数一定不是旋转排序数组的最小值，因此可以把中间数右边的数字排除，但是中间数有可能是整个数组的最小值，就如本例子，因此下一轮搜索区间是[left,mid] ,于是右边界 right = mid

从例 3 和例 4 可以看出，不论中间数比右边界大，还是中间数比右边界小，我们都可以排除掉将近一半的元素，把原始问题转换成一个规模更小的子问题，这正是“减而治之”思想的体现，因此思路 2 可行。

代码实现：

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
class Solution {
    public int findMin(int[] nums) {
        int len = nums.length;

        if (nums.length == 0){
            throw new IllegalArgumentException("数组为空，无最小元素");
        }

        int left  = 0;
        int right = nums.length - 1;

        while (left < right){
            int mid = (left + right) >>> 1;

            if (nums[mid] > nums[right]){
                left = mid + 1;
            }else {
                // nums[mid] < nums[right](不存在重复的数字)
                right = mid;
            }
        }
        // 一定存在最小元素，因此无需再做判断
        return nums[left];
    }
}

复杂度分析：

  • 时间复杂度：O(logn)
  • 空间复杂度：O（1）

题目6 ： 154. 寻找旋转排序数组中的最小值 II

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

注意数组中可能存在重复的元素。

1
2
3
4
5
6
7
8
示例 1：

输入: [1,3,5]
输出: 1
示例 2：

输入: [2,2,2,0,1]
输出: 0

代码实现：

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
// 跟153题相比
// 数组中可能存在重复的元素。
class Solution {
    public int findMin(int[] nums) {
        int len = nums.length;

        if (nums.length == 0){
            throw new IllegalArgumentException("数组为空，无最小元素");
        }

        int left  = 0;
        int right = nums.length - 1;


        while (left < right){
            int mid = (left + right) >>> 1;

            if (nums[mid] > nums[right]){
                // 说明左侧是升序序列
                // 下一轮搜索区间[mid,right]
                left = mid + 1;
            }else if (nums[mid] < nums[right]){
                // 下一轮搜索区间[left,mid]
                right = mid;
            }else {
                // nums[mid] == nums[right]
                // 例 5：[0, 1, 1, 1, 1, 1, 1]
                // 例 6：[1, 1, 1, 1, 0, 1, 1]
                // 目标值可能在中间数的左边，也有可能在中间数的右边
                // 此时看到了右边界，就把右边界排除掉就好了
                // 正是因为右边界和中间数相等，你去掉了右边界，中间数还在，就让中间数在后面的循环中再起效果
                right--;
            }
        }
        return nums[left];
    }
}

复杂度分析：

  • 时间复杂度：O(logn) ,这里不太确定，因为right– 的操作。
  • 空间复杂度：O（1）

题目7 ： H指数 II

题目描述

给定一位研究者论文被引用次数的数组（被引用次数是非负整数），数组已经按照升序排列。编写一个方法，计算出研究者的 h 指数。

h 指数的定义: “h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数不多于 h 次。）”

1
2
3
4
5
6
示例:

输入: citations = [0,1,3,5,6]
输出: 3 
解释: 给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
     由于研究者有 3 篇论文每篇至少被引用了 3 次，其余两篇论文每篇被引用不多于 3 次，所以她的 h 指数是 3。

说明:

如果 h 有多有种可能的值 ，h 指数是其中最大的那个。

进阶：

这是 H指数 的延伸题目，本题中的 citations 数组是保证有序的。
你可以优化你的算法到对数时间复杂度吗？

方法：二分查找

题目中说到：

本题中的 citations 数组是保证有序的。

并且还暗示

你可以优化你的算法到对数时间复杂度吗？

  • 因此，可以使用二分查找，二分查找这种非对即错的问题，个人觉得根据示例分析是一种不错的方法。

    • 就根据示例citations = [0, 1, 3, 5, 6]。
    • 中位数是3，citations[2] 恰好也等于 3，这个 3 正好是边界，不太好分析 ，我把中位数改成了 2。
    • 即： citiations = [0,1,2,5,6] 此时根据题目的意思，此时索引位2的那篇论文不能计入 h 指数（因为，如果算进去，则有3篇论文，但是这篇最小引用的文章才被引用两次）

  • 因此，分析出 h 指数和以下两个指标有关：

    • 某个索引 i 的 citiations 的取值
    • 某个索引 i 到 citiations 末尾的长度，即区间[i, len - 1] 的长度，即 len - 1 -i + 1 = len - i。

  • 如果nums[i] < len - i 索引 i 必须后移一位，因此候选区间是[i + 1,len - 1]

    • 所以二分查找的下一轮区间是left = i + 1

  • 如果 nums[i] > len - i的反面一定就是 right = mid ,看到 left = i + 1,可以知道分支排除了中位数，所以不会有死循环。

  • 最后，返回的是区间的长度，区间长度是 len - i

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
// 二分查找
// 思路：看nums[mid] 和 区间[mid,len - 1] 的长度
// 即 len - 1 - mid + 1 = len - mid
// [0, 1, 2, 5, 6] 为例子
class Solution {
    public int hIndex(int[] citations) {
        int len = citations.length;
        // 特判
        if (len == 0 || citations[len - 1] == 0){
            return 0;
        }

        int left  = 0;
        int right = len - 1;
        while (left < right){
            int mid = (left + right) >>> 1;
            // 如果当前的h指数比长度小就去掉这个值
            if (citations[mid] < len - mid){
                // 下一轮搜索区间
                left = mid + 1;
            }else {
                // citations[mid] >= len - mid
                // 比长度大是满足的，应该让mid 往左走尝试看有没有更小的mid值
                // 可以满足mid 对应值大于等于从[mid,len - 1]的长度
                right = mid;
            }
        }
        return len - left;
    }
}

复杂度分析

  • 时间复杂度：O(logN) N是数组的长度
  • 空间复杂度：O(1)

题目8 ： H 指数

给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。

h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数 不超过 h 次。）

例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇。

示例：

1
2
3
4
输入：citations = [3,0,6,1,5]
输出：3 
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

提示：本题和上述的区别是不是升序的数组

算法思路

  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
class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);

        int len = citations.length;
        // 特判
        if (len == 0 || citations[len - 1] == 0) {
            return 0;
        }


        int left  = 0;
        int right = citations.length - 1;

        while (left < right){
            int mid = (left + right) >>> 1;

            // 比后面的长度小就去掉这个值
            // 区间长度[mid,len - 1]
            // len - 1 - mid + 1
            if (citations[mid] < len - mid){
                left = mid + 1;
            }else {
                // 比后面的长度大，满足条件，下一轮搜索区间[left,right]
                right = mid;
            }
        }

        // 返回的是这个区间的长度(h指数)
        return len - left;
    }
}

复杂度分析：

  • 时间复杂度：O(nlogn)
  • 空间复杂度： O（1）

题目9 ： 山脉数组中查找目标值 （困难）

题目描述

（这是一个 交互式问题 ）

给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。

如果不存在这样的下标 index，就请返回 -1。

你将 不能直接访问该山脉数组，必须通过 MountainArray 接口来获取数据：

1
2
MountainArray.get(k) - 会返回数组中索引为k 的元素（下标从 0 开始）
MountainArray.length() - 会返回该数组的长度

注意：

对 MountainArray.get 发起超过 100 次调用的提交将被视为错误答案。此外，任何试图规避判题系统的解决方案都将会导致比赛资格被取消。

为了帮助大家更好地理解交互式问题，我们准备了一个样例 “答案”：https://leetcode-cn.com/playground/RKhe3ave，请注意这 不是一个正确答案。

方法：三次二分查找

  • 理解什么是山脉数组，山脉数组可以分为两部分，一部分是前有序数组，一部分是后有序数组
  • “前有序数组” 是升序数组，后有序数组是降序数组。
  • 题目还告诉我们 “对 MountainArray.get 发起超过 100 次调用的提交将被视为错误答案” ，就在疯狂暗示你使用时间复杂度低的算法，对于有序数组当然使用 “二分查找法” 。

算法思路

  • 求解这道题分为三部分
    • 第一步：先找到mountaintop 所在的索引
    • 第二步：在前有序数组中找target所在的索引，如果找到了就返回，没有找到执行步骤3
    • 第三步：如果步骤2 找不到，就在后有序降序数组中找target 所在的索引
  • 写出来的 3 个辅助方法的分支逻辑出奇地一样，在取中位数的时候，都取左中位数，才不会发生死循环。
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
/**
 * // This is MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 */

interface MountainArray {
    public int get(int index);

    public int length();
}


class MountainArrayImpl implements MountainArray {
    private int[] arr;
    private int size;

    public MountainArrayImpl(int[] arr) {
        this.arr = arr;
        this.size = this.arr.length;
    }

    @Override
    public int get(int index) {
        return this.arr[index];
    }

    @Override
    public int length() {
        return this.size;
    }

}

class Solution {

    // 特别注意：3 个辅助方法的分支出奇地一样，因此选中位数均选左中位数，才不会发生死循环

    public int findInMountainArray(int target, MountainArray mountainArr) {
        int size = mountainArr.length();
        // 步骤 1：先找到山顶元素所在的索引
        int mountaintop = findMountaintop(mountainArr, 0, size - 1);
        // 步骤 2：在前有序且升序数组中找 target 所在的索引
        int res = findFromSortedArr(mountainArr, 0, mountaintop, target);
        if (res != -1) {
            return res;
        }
        // 步骤 3：如果步骤 2 找不到，就在后有序且降序数组中找 target 所在的索引
        return findFromInversedArr(mountainArr, mountaintop + 1, size - 1, target);
    }

    private int findMountaintop(MountainArray mountainArr, int l, int r) {
        // 返回山顶元素
        while (l < r) {
            int mid = l + (r - l) / 2;
            // 取左中位数，因为进入循环，数组一定至少有 2 个元素
            // 因此，左中位数一定有右边元素，数组下标不会发生越界
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                // 如果当前的数比右边的数小，它一定不是山顶
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        // 根据题意，山顶元素一定存在，因此退出 while 循环的时候，不用再单独作判断
        return l;
    }

    private int findFromSortedArr(MountainArray mountainArr, int l, int r, int target) {
        // 在前有序且升序数组中找 target 所在的索引
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (mountainArr.get(mid) < target) {
                l = mid + 1;
            } else {
                r = mid;
            }

        }
        // 因为不确定区间收缩成 1个数以后，这个数是不是要找的数，因此单独做一次判断
        if (mountainArr.get(l) == target) {
            return l;
        }
        return -1;
    }

    private int findFromInversedArr(MountainArray mountainArr, int l, int r, int target) {
        // 在后有序且降序数组中找 target 所在的索引
        while (l < r) {
            int mid = l + (r - l) / 2;
            // 与 findFromSortedArr 方法不同的地方仅仅在于由原来的小于号改成大于好
            if (mountainArr.get(mid) > target) {
                l = mid + 1;
            } else {
                r = mid;
            }

        }
        // 因为不确定区间收缩成 1个数以后，这个数是不是要找的数，因此单独做一次判断
        if (mountainArr.get(l) == target) {
            return l;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 3, 1};
        int target = 3;
        MountainArray mountainArray = new MountainArrayImpl(arr);

        Solution solution = new Solution();
        int res = solution.findInMountainArray(target, mountainArray);
        System.out.println(res);
    }
}

复杂度分析

  • 时间复杂度（OlogN）二分查找法的时间复杂度是对数级别的，这里使用了 3 次二分查找法，是常数倍数，因此可以忽略这个常数系数。
  • 空间复杂度：O(1) 里使用的额外的辅助空间仅仅是 mountaintop、中位数索引 mid 等，是常数级别，因此空间复杂度为 O(1)。

3. 分类2：在一个有范围的区间内找到一个整数

题目1 ： 69：x 的平方根

题目描述

  • 实现 int sqrt(int x) 函数。
  • 计算并返回 x 的平方根，其中 x 是非负整数。
  • 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

1
2
输入: 4
输出: 2

示例 2:

1
2
3
4
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

算法思路:二分查找

  • 二分查找法要找到左右边界
  • 一个数的平方根肯定不会超过它自己，还有比较细节的划分，那就是一个数的平方根不会超过它的一半。（比如8的平方根，一半是4，4的平方是16，大于8）
  • 因此我们要计算一下，这个右边界是多少

mark

意思就是：如果一个数的一般平方大于自己，那么这个数的取值范围。解以上不等式得 a >= 4 或者 a < 0

  • 于是右边界的值就是4，因为边界值要大于0
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
class Solution {
    public int mySqrt(int x) {
        // 对0的特殊处理
        if (x == 0){
            return 0;
        }

        // 要把搜索的区间设置成长整型
        // 注意：针对特殊测试用例，例如 2147395599
        long left = 1;
        long right = x/2;

        while (left < right){
            long mid = (left + right + 1) >>> 1;

            long square = mid * mid;

            // 排除大于不是解
            if (square > x){
                right = mid - 1;
            }else {
                left = mid;
            }
        }
        // 注意返回的是整型
        return (int) left;
    }
}

复杂度分析

  • 时间复杂度：O(logN),二分查找的时间复杂度是对数级别的
  • 空间复杂度：O(1) 使用了常数个数的辅助空间用于存储

题目2： 287. 寻找重复数

题目描述

  • 给定一个包含 n + 1个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

1
2
输入: [1,3,4,2,2]
输出: 2

示例 2:

1
2
输入: [3,1,3,4,2]
输出: 3

说明：

  • 不能更改原数组（假设数组是只读的）。
  • 只能使用额外的 O(1) 的空间。
  • 时间复杂度小于 O(n^2) 。
  • 数组中只有一个重复的数字，但它可能不止重复出现一次。

Solution：二分法

  • 如果测试数据不在这个范围里，二分法失效。

  • 二分法的常见作用：可以用来确定一个有范围的整数

  • 预备知识：

抽屉原理：假设要把10个苹果放进9个柜子，那么一定有一个柜子放了不止一个。

容易想到的方法有：

  • 使用哈希表判重，这违反了限制 2；
  • 将原始数组排序，排序以后，重复的数相邻，即找到了重复数，这违反了限制 1；
  • 使用类似「力扣」第 41 题：缺失的第一个正数 （原地哈希）的思路，当两个数发现要放在同一个地方的时候，就发现了这个重的元素，这违反了限制 1；
  • 既然要定位数，这个数恰好是一个整数，可以在「整数的有效范围内」做二分查找，但是比较烦的一点是得反复看整个数组好几次，本题解就介绍通过二分法定位一个有范围的整数；
  • 还可以使用「快慢指针」来完成，不过这种做法太有技巧性了，不是通用的做法，可以查看官方题解。

思路：

  • 二分法的思路是先猜一个数（有效范围 [left, right]里的中间数 mid）

  • 然后统计原始数组中小于等于这个中间数的元素的个数 count , 如果count 严格大于 mid ，注意我加了着重号的部分「小于等于」、「严格大于」）。

  • 根据抽屉原理，重复的元素就在区间 [left, mid] 里；

举个例子：

  • 以[2,4,5,2,3,1,6,7] 为例，一共 8 个数，n + 1 = 8 那么 n = 7 并且根据题目的意思，每个数都在[1,7]之间
  • 例如：区间[1,7]的中位数是4
    • 之后遍历整个数组，统计小于等于4的整数的个数，如果不存在重复元素，最后就是4个。
    • 等于4的时候区间[1,4]内也可能有重复的元素，比如 [1,2,2,4] 。
    • 但是,如果整个数组里小于等于4的正数的个数严格大于4 的时候，根据抽屉原理，一定说明重复的数字在[1,4]之间。

Solution : 算法

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
class Solution {
    public int findDuplicate(int[] nums) {
        int len = nums.length;

        int left  = 1;
        int right = len - 1;

        while (left < right){
            //在 Java 里可以这么用，
            // 当 left + right 溢出的时候，无符号右移保证结果依然正确
            int mid = (left + right) >>> 1;

            // 每次更新 count 会被重置为0
            int count = 0;

            // 统计原始数组中小于等于这个中间数元素的个数count
            for (int num : nums) {
                if (num <= mid){
                    count += 1;
                }
            }

            // 根据抽屉原理，count如果严格大于mid个
            // 此时重复元素一定在[1,mid]之间
            if (count > mid){
                // 重复元素位于[left,mid]之间
                right = mid;
            }else {
                // 重复元素位于[mid + 1, right] 之间
                left = mid + 1;
            }
        }
        // left = right 的时候推出循环，结果就是重复的数字
        return left;
    }
}
  • 时间复杂度：O(nlogn) - 二分法的时间复杂度是O(logn) ,并且在二分法内部执行了一次 for 循环 ，时间复杂度是O(n), 所以总的复杂度是O(nlogn)。
  • 空间复杂度O(1) : 使用了一个count变量

题目3 ： 374. 猜数字大小

题目描述

我们正在玩一个猜数字游戏。 游戏规则如下：
我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。
每次你猜错了，我会告诉你这个数字是大了还是小了。
你调用一个预先定义好的接口 guess(int num)，它会返回 3 个可能的结果（-1，1 或 0）：

1
2
3
-1 : 我的数字比较小
 1 : 我的数字比较大
 0 : 恭喜！你猜对了！

示例 :

1
2
输入: n = 10, pick = 6
输出: 6

算法思想：

  1. 首先得先把guessnum接口先写出来
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class GuessGame{
    // 比如我猜的数字是6
    private static final int NUM = 6;

    int guess(int num){
        // 你和我猜的一样
        if (num == NUM){
            return 0;
        }else if (num < NUM){
            // 你猜的比我猜的小
            return -1;
        }
        // 你猜的比我猜的大
        return 1;
    }
}
  1. 接下来的思路就很显然了
    • 排除猜错的区间 guessNum = -1 的情况，那么下一轮搜索区间是[left,mid - 1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution extends GuessGame {
    public int guessNumber(int n){
        int left  = 1;
        int right = n;

        while (left < right){
            int mid = (left + right + 1) >>> 1;

            int guessNum = guess(mid);
            if (guessNum == -1){
                // 中位数比猜的数大
                right = mid - 1;
            }else {
                left = mid;
            }
        }
        // 最后一定会猜对
        return left;
    }
}
  • 时间复杂度：O(logn)
  • 空间复杂度： O(1)

题目4 ： 1300. 转变数组后最接近目标值的数组和

题目描述

给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差的绝对值最小）。

如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。

请注意，答案不一定是 arr 中的数字。

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

输入：arr = [4,9,3], target = 10
输出：3
解释：当选择 value 为 3 时，数组会变成 [3, 3, 3]，和为 9 ，这是最接近 target 的方案。


示例 2：

输入：arr = [2,3,5], target = 10
输出：5


示例 3：

输入：arr = [60864,25176,27249,21296,20204], target = 56803
输出：11361

提示：

  • 1 <= arr.length <= 10^4
  • 1 <= arr[i], target <= 10^5

方法：二分查找

思路：

  • 使用二分法确定一个正数threshold,使得这个threshold下，转变后的数组的和最接近目标值target
    • 转变的规则是严格大于threshold元素变成threshold，那么也就意味着threshold越大，数组的和越大（注意这里是单调的，也有可能threshold扩大之后，和可能不变，也就是大于等于的关系）
  • 正是因为题目说 value 是整数，并且「答案不一定是 arr 中的数字」，因此依然可以使用二分查找法确定这个整数值。

mark

  • 做题的时候，发现最难写的其实是判断的条件，因为「怎么衡量接近」，度量这个「最接近」的量不好选。因此需要考虑别的方案；
  • 这里问题就是：选定了一个value求和之后，
    • 如果恰恰好等于 target ，那就万事大吉
    • 不过更可能出现的情况是， value 取小了，接近程度变大
    • 而value 取大了之后，接近程度变小了

mark

  • 解决方案
    • 先用二分法确定value的可能的值
    • 然后把value的上下边界都拿出来进行一次比较
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
class Solution {
    public int findBestValue(int[] arr, int target) {
        int  left  = 0;
        int  right = 0;

        // 取最大的数置为right
        for (int num : arr) {
            right = Math.max(num,right);
        }

        while (left < right){
            int mid = (left + right) >>> 1;
            int sum = calculateSum(arr,mid);

            // 计算第一个使得转变后数组的和大于等于target的阈值
            if (sum < target){
                left = mid + 1;
            }else {
                right = mid;
            }
        }

        // 判断到底返回的是哪个阈值
        // 比较阈值线分别在left - 1 和 left的时候与target的接近程度
        int sum1 = calculateSum(arr,left - 1);
        int sum2 = calculateSum(arr,left);
        // 判断接近程度
        if (target - sum1 <= sum2 - target){
            return left -  1;
        }
        return left;
    }

    /// 计算数组中threshold以下数字的和
    private int calculateSum(int[] arr, int threshold) {
        int sum = 0;
        for (int num : arr) {
            sum += Math.min(num,threshold);
        }
        return sum;
    }
}



class Test{
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findBestValue(new int[]{2, 3, 5}, 10));
    }
}

复杂度分析

  • 时间复杂度：O(NlogN)，这里 N 是输入数组的长度，二分的时间复杂度是 O(logN)，每一次 calculateSum 的时间复杂度是 O(N)；

  • 空间复杂度：O(1)。

题目5 ： 1283. 使结果不超过阈值的最小除数

题目描述

  • 给你一个整数数组 nums 和一个正整数 threshold，选择一个正整数作为除数，然后将数组里的每个数都除以它，并对除法结果求和。
  • 请你找出能够使得上述结果小于等于阈值 threshold 的除数最小的那个
  • 每个数除以除数之后都会向上取整，比方说 7/3 = 3 ， 10/2 = 5 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
示例 1：

输入：nums = [1,2,5,9], threshold = 6
输出：5
解释：如果除数为 1 ，我们可以得到和为 17 （1+2+5+9）。
如果除数为 4 ，我们可以得到和为 7 (1+1+2+3) 。如果除数为 5 ，和为 5 (1+1+1+2)。

    
示例 2：

输入：nums = [2,3,5,7,11], threshold = 11
输出：3

示例 3：

输入：nums = [19], threshold = 5
输出：4

方法思路

  1. 找出小于等于阈值 threshold 中最小的那个，明显可以使用二分查找
  2. 于是可以思考除数最大可以是多少，最小是多少
    • 最大是数组中最大的那个数，因为除数如果再大，整除以后每个数都得 1（上取整的缘故）；
    • 最小可以是 1。
  1. 写 if 分支的时候，根据题目的意思选
    • 选择一个正整数作为除数，然后将数组重的每个数都除以它，并对除法结果求和
  2. 这时候开始思考二分查找的关键 ： 排除什么时候不是解
    • 因此 ： 和严格大于 阈值threshold 的整数，一定不是解。根据减而治之的思想， 定位这个除数。

代码实现

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
public class Solution {

    public int smallestDivisor(int[] nums, int threshold) {
        // 先找数组中的最大值，用最大值作为除数，除完以后和最小
        int maxVal = 1;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        // 注意：最小值是 1，因为 threshold 可以很大
        int left = 1;
        int right = maxVal;

        while (left < right) {
            int mid = (left + right) >>> 1;

            if (calculateSum(nums, mid) > threshold) {
                // sum 大于阈值一定不是解，说明除数选得太小了
                // 下一轮搜索区间是 [mid + 1, right]
                // （把下一轮搜索区间写出来，边界选择就不会错）
                left = mid + 1;
                // 边界是 left = mid + 1 ，中间数不用上取整
            } else {
                right = mid;
            }
        }
        return left;
    }

    /**
     * @param nums
     * @param divisor
     * @return 数组中各个元素与 divisor 相除的结果（向上取整）之和
     */
    private int calculateSum(int[] nums, int divisor) {
        int sum = 0;

        for (int num : nums) {
            sum += num / divisor;

            // 注意：不能整除的时候，需要向上取整
            if (num % divisor != 0) {
                sum++;
            }
        }
        return sum;
    }
}

复杂度分析

  • 时间复杂度：ONlogmaxnums 这里 N 是数组的长度，每一次二分都执行了边界判断函数，都得遍历一遍数组；
  • 空间复杂度：O(1)。

题目6 ： 875. 爱吃香蕉的珂珂

题目描述

珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

思路

  • 最小速度是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
class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        // 得到速度的最大值
        int maxVal = 1;
        for (int pile : piles) {
            maxVal = Math.max(maxVal,pile);
        }

        // 速度的最小值
        int left  = 1;
        // 速度的最大值
        int right = maxVal;


        while (left < right){
            int mid = (left + right) >>> 1;

            // 排除：吃的太慢的情况
            if (calculateSum(piles,mid) > H){
                // 下一轮搜索区间[mid + 1,right]
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return left;
    }

    private int calculateSum(int[] piles,int speed){
        int sum = 0;
        for (int pile : piles) {
            // 除不尽向上取整
            sum += pile / speed;
            if(pile % speed != 0){
                sum += 1;
            }
        }
        return sum;
    }
}

复杂度分析

  • 时间复杂度：ONlogmaxnums 这里 N 是数组的长度，每一次二分都执行了边界判断函数，都得遍历一遍数组；
  • 空间复杂度：O(1)。
打赏
  • 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！
  • © 2019-2022 Zhuuu
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信