6.2 二分查找
前言
二分查找的思想非常简单，在有序的数据中每次按照中点进行尝试，如果中间点大于我们要查找的值，则答案应该位于左侧， 反之右侧。由于每次可以排除现有数据量的一半，因此时间复杂度是O(logn)。
以下我们提供两套二分查找的模板。两个模板的原理都是一样的，区别在于边界的处理。二分查找的难点往往也在于边界。因此如果我们划分的边界是[l,mid]和[mid + 1, r]那我们选择模板1。如果我们划分的边界是[0,mid-1]和[mid,r] 那我们选择模板2。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| int bsec1(int l, int r)
{
while (l < r)
{
int mid = (l + r)/2;
if (check(mid)) r = mid;
else l = mid + 1;
}
return r;
}
int bsec2(int l, int r)
{
while (l < r)
{
int mid = ( l + r + 1 ) /2;
if (check(mid)) l = mid;
else r = mid - 1;
}
return r;
}
|
1
2
3
4
5
6
7
| int lf = 0, rt = nums.length - 1;
while (lf < rt) {
int mid = (lf + rt) >> 1;
if (nums[mid] >= target) rt = mid;
else lf = mid + 1;
}
return nums[rt] == target ? rt : -1;
|
1
2
3
4
5
6
7
8
| int lf = 0, rt = nums.length - 1;
while (lf <= rt) {
int mid = (lf + rt) >> 1;
if (cur == target) return mid;
else if (cur > target) rt = mid - 1;
else lf = mid + 1;
}
return lf;
|
1
2
3
4
5
6
7
| int lf = 0, rt = n - 1;
while (lf < rt) {
int mid = ((lf - rt) >> 1) + rt;
if (cur > target) rt = mid;
else lf = mid + 1;
}
return rt;
|
1
2
3
4
5
6
7
| int lf = 0, rt = x;
while (lf < rt) {
int mid = (lf + rt) >> 1;
if (check(mid)) rt = mid;
else lf = mid + 1;
}
return rt;
|
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 示例 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
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
|
题目解析
由于数组是有序的，因此可以使用二分进行查找。
假设说 nums[mid] >= target ，则说明此时应该在 [lf, mid] 中寻找答案，那么r = mid；因此我们套用模板二即可。
当然如果不存在应该返回-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
| class Solution {
public int search(int[] nums, int target) {
int lf = 0, rt = nums.length - 1;
while (lf < rt) {
int mid = (lf + rt) >> 1;
if (nums[mid] >= target) {
rt = mid;
} else {
lf = mid + 1;
}
}
return nums[rt] == target ? rt : -1;
}
}
|
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
1
2
3
4
5
6
7
8
9
10
11
| 示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 2^31 - 1
|
题目解析
由于不能使用库函数，因此我们需要“对答案进行二分”。
答案可能的范围是 [0, x]，因此我们要二分的思路枚举这个区间。
但是要舍去小数的部分，换个说法就是找到区间 [0, x] 中小于等于x的最大值。
最小值最大的问题也是二分的一个经典标志。
如果 mid^2 大于等于 x，则说明此时应该在 [l, mid] 之间找答案，反之则是 [mid + 1, r] 。因此套用模板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
26
27
| class Solution {
public int mySqrt(int x) {
int lf = 0, rt = x;
while (lf < rt) {
int mid = (lf + rt) >> 1;
long cur = (long) mid * mid;
if (cur >= x) {
rt = mid;
} else {
lf = mid + 1;
}
}
return (long)rt * rt == x ? rt : rt - 1;
}
}
|
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(logn) 的算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
提示:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 为 无重复元素 的 升序 排列数组
-10^4 <= target <= 10^4
|
题目描述
等价于找到大于等于 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
| class Solution {
public int searchInsert(int[] nums, int target) {
int lf = 0, rt = nums.length;
while (lf < rt) {
int mid = (lf + rt) >> 1;
if (nums[mid] >= target) {
rt = mid;
} else {
lf = mid + 1;
}
}
return rt;
}
}
|
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 示例 1：
输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
示例 2：
输入：n = 1, bad = 1
输出：1
提示：
1 <= bad <= n <= 2^31 - 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
| public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int l = 1, r = n;
while (l < r) {
int mid = ((l - r) >> 1) + r;
if (isBadVersion(mid)) {
r = mid;
}
else {
l = mid + 1;
}
}
return r;
}
}
|
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(logn) 的算法来解决此问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5， 其峰值元素为 6。
提示：
1 <= nums.length <= 1000
- 2^31 <= nums[i] <= 2^31 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 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
| class Solution {
public int findPeakElement(int[] nums) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = ((l - r) >> 1) + r;
if (nums[mid] < nums[mid + 1]) {
l = mid + 1;
} else {
r = mid;
}
}
return r;
}
}
|
珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。
珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 示例 1：
输入：piles = [3,6,7,11], h = 8
输出：4
示例 2：
输入：piles = [30,11,23,4,20], h = 5
输出：30
示例 3：
输入：piles = [30,11,23,4,20], h = 6
输出：23
提示：
1 <= piles.length <= 10^4
piles.length <= h <= 10^9
1 <= piles[i] <= 10^9
|
题目解析
代码展示
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
| class Solution {
public int minEatingSpeed(int[] piles, int h) {
long sum = 0;
for (int pile : piles) {
sum += pile;
}
long l = 1, r = sum;
while (l < r) {
long mid = ((l - r) >> 1) + r;
if (check(mid, piles, h)) {
r = mid;
} else {
l = mid + 1;
}
}
return (int)r;
}
boolean check(long x, int[] piles, int h) {
int cnt = 0;
for (int pile : piles) {
if (pile % x == 0) {
cnt += pile / x;
} else {
cnt += (pile / x) + 1;
}
}
return cnt <= h;
}
}
|
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true，否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
进阶：不要 使用任何内置的库函数，如 sqrt 。
1
2
3
4
5
6
7
8
9
10
| 示例 1：
输入：num = 16
输出：true
示例 2：
输入：num = 14
输出：false
提示：
1 <= num <= 2^31 - 1
|
题目解析
由于不能使用库函数，因此我们需要对答案进行二分。
初始的二分区间可以定义为[0, num]。
代码展示
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
| class Solution {
public boolean isPerfectSquare(int num) {
int l = 0, r = num;
while (l < r) {
int mid = ((l - r) >> 1) + r;
if ((long)mid * mid >= num) {
r = mid;
} else {
l = mid + 1;
}
}
return r * r == num;
}
}
|
给你一个排序（非递减顺序）后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。如果不存在这样的字符，则返回 letters 的第一个字符。
在比较时，字母是依序循环出现的。举个例子：
如果目标字母 target = ‘z’ 并且字符列表为 letters = [‘a’, ‘b’]，则答案返回 ‘a’
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 示例 1：
输入: letters = [“c”, “f”, “j”]，target = “a”
输出: “c”
示例 2:
输入: letters = [“c”,“f”,“j”], target = “c”
输出: “f”
示例 3:
输入: letters = [“c”,“f”,“j”], target = “d”
输出: “f”
提示：
2 <= letters.length <= 10^4
letters[i] 是一个小写字母
letters 按非递减顺序排序
letters 最少包含两个不同的字母
target 是一个小写字母
|
题目解析
此题转换为：找到数组中第一个大于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
| class Solution {
public char nextGreatestLetter(char[] letters, char target) {
int l = 0, r = letters.length - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (letters[mid] > target) {
r = mid;
} else {
l = mid + 1;
}
}
if (letters[r] > target) {
return letters[r];
} else {
return letters[0];
}
}
}
|
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
0 <= nums.length <= 10^5
- 10^9 <= nums[i] <= 10^9
nums 是一个非递减数组
- 10^9 <= target <= 10^9
|
代码展示
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
| class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0) return new int[]{-1, -1};
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
if (nums[r] != target) return new int[]{-1, -1};
int first = r;
l = 0;
r = nums.length - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (nums[mid] > target) r = mid - 1;
else l = mid;
}
return new int[]{first, r};
}
}
|
给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 示例 1：
输入：nums = [7,2,5,10,8], m = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
示例 2：
输入：nums = [1,2,3,4,5], m = 2
输出：9
示例 3：
输入：nums = [1,4,4], m = 3
输出：4
提示：
1 <= nums.length <= 1000
0 <= nums[i] <= 10^6
1 <= m <= min(50, nums.length)
|
代码展示
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
| class Solution {
public int splitArray(int[] nums, int m) {
int sum = 0;
for (int num : nums) {
sum += num;
}
int l = 0, r = sum;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid, nums, m)) {
r = mid;
} else {
l = mid + 1;
}
}
return r;
}
boolean check(int x, int[] nums, int m) {
int cnt = 1;
int cur = 0;
for (int i = 0; i < nums.length; i++) {
if (cur + nums[i] <= x) {
cur += nums[i];
} else {
if (nums[i] > x) {
return false;
}
cur = nums[i];
cnt++;
}
}
return cnt <= m;
}
}
|