Abo

二分查找解题模版与题型 🎈

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

记住不完备的二分算法写法所导致的死循环跟跳过查找的特例 🙄

wallhaven-nmy7o1

愿岁月静好,安然若素

前言

二分查找(Binary Search)算是最为基本的一个算法,也比较容易掌握。但是有些时候,我们可能因为一些细节的点没有考虑而导致程序出错,虽然这个算法比较简单,但文章也会有比较高级的应用,比如按值二分:近似sqrt操作。

什么是二分查找?

比二分查找更简单的算法,我能想到的只有遍历枚举,说的直白些,就是 for 循环遍历而已。

我们通常需要在一个数组当中找一个数,这个时候我们可以写一个 for 循环去挨个查找,这么下来,时间复杂度就会是O(n)

如果我告诉你,这个数组是排序好的,这时我们就可以使用二分查找去找这个数。

我们可以选择数组中间的元素,这个中间元素会把数组分成前后两个相等的区间,如果我们要找的元素比中间元素要大,证明这个元素只可能在后半部分区间,我们就只需要去到后半部分区间用类似的方法再次查找。

如果比中间元素要小,则需要去到前半部分区间用类似的方法再次查找,直到最后我们找到了,或者说整个数组给分完了(没找到)

这样的话时间复杂度是 O(logn)

关于时间复杂度跟空间复杂度,详细见另一篇文章)

你可以形象地理解每次操作我们都把数组对折,形成一个新的数组,因此二分查找又叫做折半查找。相信有一定编程基础的人都能够理解这个算法,我们的重点将会放在具体的实现和题型上面。

下面划重点

二分查找模板

1
2
3
4
5
6
7
8
9
10
int start = 0, end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
// mid = start + ((end - start) >>> 1);
if (...) {
start = mid;
} else {
end = mid;
}
}

首先解释一下,上面模版当中的 start + (end - start) / 2,这里不直接写成 (end + start) / 2的目的是防止计算越界,举个例子,假如 end = 2^31 - 1, start = 100,如果是后一种写法的话就会在计算 end + start 的时候越界,导致结果不正确。

二分查找算法若没实现好的两种后果

  • 死循环
  • 跳过了本该查找的位置

死循环

1
2
3
4
比如区间定为[22],需查元素为3,此时套用下方代码就会导致死循环
mid 计算后都会等于 start 的初始值
然后将 mid 赋值给 start,导致 start 和 end 一直紧挨在一起
这时就会导致死循环.
1
2
3
4
5
6
7
8
9
10
// start + 1 < end  => start < end   error
int start = 0, end = nums.length - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (...) {
start = mid;
} else {
end = mid;
}
}

故有些人就会认为,那好,就每次赋值的时候把mid往后移动一格就好了,于是乎就变成下面的形式:

跳过本该查找的位置

1
2
3
4
5
6
7
8
9
10
int start = 0, end = nums.length - 1;
while (start < end) {
int mid = start + (end - start) / 2;

if (...) {
start = mid + 1;
} else {
end = mid - 1;
}
}

哦吼,似乎例子通过了,但是还会存在一个新的问题,现在来思考这么一个问题“在一个允许重复元素的按升序排好序的数组中,返回元素的index,如果有重复,就返回最大的那个index”

比如[1,2,2,3]这个例子中,假如我们要找的元素的值是2,那么正确的返回值应该是2,也就是第二个2的index,如果我们使用上面的模板,最后的程序就会变成:

1
2
3
4
5
6
7
8
9
10
int start = 0, end = nums.length - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (nums[mid] <= target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
//根据条件返回 end 或者 start

通过手写模拟观察,可以得到我们最后返回的值是3,这就是我们之前提到的 跳过本该查找的位置 的情况。网上还有一种很常见的模版,就是把 while 循环中的条件设为 start <= end,如果用来实现上面这个问题,就会是:

1
2
3
4
5
6
7
8
9
10
11
int start = 0, end = nums.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] <= target) {
start = mid + 1;
} else {
end = mid - 1;
}
}

根据条件返回 end 或者 start

易发现,此时end指针所指向的位置即是我们要寻找的位置,在这个模板中,while循环结束后,end + 1 == start 这个等式一直都是成立,仅需满足数组长度不为0的条件。

但是这个模板也有不良之处: 如果输入数组为[1],那么while循环结束后,要么是start超出数组范围,要么是end变成-1,所以就会导致你不仅需要判断 start 和 end 对应的元素是不是要找的元素,还需要判断 start 和 end 是否在合法的范围内,所以上面的模板固然好,但是还是要知道存在数组越界的漏洞的!

万变不离其宗,我们回到原先的代码

1
2
3
4
5
6
7
8
9
10
int start = 0, end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;

if (...) {
start = mid;
} else {
end = mid;
}
}

此时我们不需要关注 是否需要 mid +/- 1 ,也不需要去判断 while 循环后的 start、end 是否合法,具体问题我们只需要套模版即可。

下面实战演练看看:

一般分两步:

  1. if-else条件里面分别放置什么内容
  2. 返回要找的元素,是end,还是start?

小试牛刀:刷题

第一个错误的版本

题目来源于 LeetCode 上第 278 号问题:第一个错误的版本。题目难度为 Easy,目前通过率为 32.9%

题目描述

你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例:

1
2
3
4
5
给定 n = 5,并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以,4 是第一个错误的版本。

思考

其实题目就是要找最先出现的元素,在这种情况下,如果我们找到了元素,依旧不知道它是不是最先(小)的,但是我们知道答案肯定不在后面,肯定在这或者是之前,因此这种情况需要将尾指针往前移。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int firstBadVersion(int n) {
int start = 0, end = n;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (isBadVersion(mid)) {
end = mid;
} else {
start = mid;
}
}
if (isBadVersion(start)) {
return start;
}
return end;
}

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

题目来源于 LeetCode 上第 34 号问题:在排序数组中查找元素的第一个和最后一个位置。题目难度为 Easy,目前通过率为 37.4% 。

题目描述

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

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

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

示例 1:

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

示例 2:

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

思考

给定一个元素,要找其最先出现的 index,还要找其最后出现的 index。这道题把之前的两个问题合在了一起。我们只需要用两次二分查找,一次找前,一次找后。(第一个错误的版本+最后一个错误的版本的亚子)

仔细看的话,你会发现,这道题其实 就是在找一个元素在数组中出现的范围,因为数组有序,所以这个范围是连续的。

代码实现

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
public int[] searchRange(int[] nums, int target) {
int[] result = new int[]{-1, -1};
if (nums == null || nums.length == 0) {
return result;
}

// find front
int start = 0, end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] >= target) {
end = mid;
} else {
start = mid;
}
}

if (nums[start] == target) {
result[0] = start;
} else if (nums[end] == target) {
result[0] = end;
}

// find back
start = 0; end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] <= target) {
start = mid;
} else {
end = mid;
}
}

if (nums[end] == target) {
result[1] = end;
} else if (nums[start] == target) {
result[1] = start;
}

return result;
}

搜索二维矩阵

题目来源于 LeetCode 上第 74 号问题:搜索二维矩阵。题目难度为 Medium,目前通过率为 35.7% 。

题目描述

编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

示例 1:

1
2
3
4
5
6
7
8
输入:matrix = 
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true

示例 2:

1
2
3
4
5
6
7
8
输入:matrix = 
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
输出: false

思考

我们需要去判断一个元素在不在矩阵中,这个矩阵是排序好的,前一行的元素都比后一行的元素小,在同一行中,元素也是从小到大排列的。这个问题也很简单,我们先找行,再找列,但是需要注意的是,在找行的时候,你必须确保这一行开头的元素是 小于等于 你要找的元素的,不然接下来的操作将会没有意义。

代码实现

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
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}

int startRow = 0, endRow = matrix.length - 1;
while (startRow + 1 < endRow) {
int mid = startRow + (endRow - startRow) / 2;
if (matrix[mid][0] == target) { //等于直接true
return true;
} else if (matrix[mid][0] < target) {
startRow = mid;
} else {
endRow = mid;
}
}

int selectRow = 0;
if (matrix[endRow][0] <= target) { // 确认是在哪一行
selectRow = endRow;
} else {
selectRow = startRow;
}

int startCol = 0, endCol = matrix[0].length - 1;
while (startCol + 1 < endCol) {
int mid = startCol + (endCol - startCol) / 2;
if (matrix[selectRow][mid] == target) { //等于直接true
return true;
} else if (matrix[selectRow][mid] < target) {
startCol = mid;
} else {
endCol = mid;
}
}

if (matrix[selectRow][startCol] == target
|| matrix[selectRow][endCol] == target) {
return true;
}

return false;
}

搜索二维矩阵 Ⅱ

题目来源于 LeetCode 上第 240 号问题:搜索二维矩阵 II。题目难度为 Medium,目前通过率为 37.4% 。

题目描述

编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

示例:

现有矩阵 matrix 如下:

1
2
3
4
5
6
7
[  
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

给定 target = 5,返回 true。

给定 target = 20,返回 false。

思考

这道题是上面那道题的变种,问题没变,主要是变在输入矩阵上,题目只保证矩阵中元素行和列是排好序的,也就是说前一行的元素不一定都比后一行的元素小,这个时候,我们之前的先找行,再找列的策略就失效了。

这个二维数组是有特点的:

  • 每一行都是递增
  • 每一列都是递增

于是可以考虑从 对角线 入手,对角线上的点往右和往下分别做二分,这样可以把时间复杂度控制在 O(2 * (1 + log2 + … + log(n)) = O(log(n!)) = O(nlog(n))

代码实现

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
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}

int numOfFind = Math.min(matrix.length, matrix[0].length);

for (int i = 0; i < numOfFind; ++i) {
boolean upDown = find(matrix, i, target, true);
boolean leftRight = find(matrix, i, target, false);

if (upDown || leftRight) {
return true;
}
}

return false;
}

private boolean find(int[][] matrix, int i, int target, boolean isFindRow) {

int start = i;
int end = isFindRow ? matrix.length - 1 : matrix[0].length - 1;

while (start + 1 < end) {
int mid = start + (end - start) / 2;

if (isFindRow) {
if (matrix[mid][i] < target) {
start = mid;
} else if (matrix[mid][i] > target) {
end = mid;
} else {
return true;
}
} else {
if (matrix[i][mid] < target) {
start = mid;
} else if (matrix[i][mid] > target) {
end = mid;
} else {
return true;
}
}
}

if (isFindRow) {
if (matrix[start][i] == target || matrix[end][i] == target) {
return true;
}
} else {
if (matrix[i][start] == target || matrix[i][end] == target) {
return true;
}
}

return false;
}

除了这种做法,还有一种 O(n) 的解法比较 tricky,

首先,我们初始化一个指向矩阵右上角的 元素

从这个元素开始查找,如果这个元素比 target 大,则说明需要找更小的,往左走;如果这个元素比 target 小,则说明应该找更大的,往下走。

20191022230241

20191022230411

登堂入室:Rotated Array 系列

系列描述

有一类题型是把一个数组向右或者向左移动了一下,比如数组 [1,2,3,4,5,6] 向右移动两格就会变成 [5,6,1,2,3,4],这样这个数组就变成了一个非排序状态。但是仔细看的话你会发现,移动后的数组变成了两截,这两截内的元素是按序排列的,比如在上面的例子中,移动后的数组就会有 [5,6] 和 [1,2,3,4] 这两个区间,这两个区间内的元素都是按序排列的。

仔细观察这两个区间,你会发现,其中一个区间内的所有元素都比另一个区间的任意元素小, 这个点就给我们二分查找创造了条件,我们可以根据尾元素作为区分值,但要清楚一点的是,没有移动过的数组也需要被你的程序考虑在内。

我们结合实际的题目来看看。

旋转数组的最小数字

题目来源于 LeetCode 上第 153 号问题:旋转数组的最小数字。题目难度为 Medium,目前通过率为 49.2% 。

题目描述

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

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

请找出其中最小的元素。

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

示例 1:

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

示例 2:

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

思考

找出转动数组中最小的值,之前讲过的转动数组的性质,这个数组其实可以看成两个排序好的数组,一前一后,一大一小, 我们做二分的时候,二分取到的中点有可能在前区间,也有可能在后区间,怎么判断?

可以使用尾元素作为区分值,二分中点对应的值比尾元素小的话那就说明二分中点是在后面的区间,大的话就会是在前面的区间。

如果中点在后面的区间,那我们就要移动尾指针,如果是在前面的区间的话,我们就要移动首指针,其实就是逐步逼近后区间首元素的一个过程。

可能很多人会有一个疑问就是,这里能不能使用首元素作为区分值,其实是不行的,考虑一个例子 [1,2,3,4,5],如果还是使用尾元素,那么整个过程就是一直移动尾指针,直到逼近答案,但是使用首元素的话,如果你还是考虑这个数组有两个区间,比首元素大证明在第一个区间,要移动首指针,这里就会出问题,我们跳过了答案。

多试几个例子,相信不难理解。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}

int start = 0, end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;

if (nums[mid] <= nums[end]) {
end = mid;
} else {
start = mid;
}
}

if (nums[start] > nums[end]) {
return nums[end];
}

return nums[start];
}

搜索旋转排序数组

题目来源于 LeetCode 上第 33 号问题:搜索旋转排序数组。题目难度为 Medium,目前通过率为 36.1% 。

问题分析

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

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

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

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

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

示例 1:

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

示例 2:

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

思考

这道题和前面那道题相比更复杂了些,我们不是要找值最小的那个元素,而是要找给定元素在数组中出现的 index。

前一道题,我们只需要判断二分中点在哪个位置即可,这里会比之前多了一个判断,就是我们要找的元素是在前后两个区间中的哪一个?

我们知道了二分中点所在的区间,以及要找的元素所在的区间后,就可以按情况移动前后指针,其实一共有下面几种情况,我用 t 表示 target,也就是我们要找的元素,用 m 表示二分中点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[...][...]         -> 二分中点在前区间,要找的元素在后区间
m t

[...][...] -> 二分钟点在后区间,要找的元素在前区间
t m

[...][...] -> 二分中点和要找的元素都在前区间,要找的元素在二分中点之后
m t

[...][...] -> 二分中点和要找的元素都在前区间,要找的元素在二分中点之前
t m

[...][...] -> 二分中点和要找的元素都在后区间,要找的元素在二分中点之后
m t

[...][...] -> 二分中点和要找的元素都在后区间,要找的元素在二分中点之前
t m

分析归分析,我们最后还是要转化成可执行的代码,写代码的时候你会发现有些情况是可以合并的:

1
2
3
4
5
6
7
8
9
10
11
[...][...] -> 要找的元素在前区间,二分中点在后区间,或者是在前区间但比要找的元素大,这时我们需要移动尾指针
t m m m

[...][...] -> 要找的元素和二分中点都在前区间,但是要找的元素比二分中点要大,这时移动首指针
m t

[...][...] -> 要找的元素在后区间,二分中点在前区间,或者是在后区间但比要找的元素小,这时我们需要移动首指针
m m m t

[...][...] -> 要找的元素和二分中点都在后区间,但是要找的元素比二分中点要小,这时移动尾指针
t m

注意思考分析的时候也需要想想,如果数组没有被转动,那么我们的思路是否正确。

代码实现

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
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}

int start = 0, end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;

if (target > nums[end]) { // ||后面理解成 nums[mid] <= target的条件下满足 nums[mid] <= nums[end]😷
if (nums[mid] > target || nums[mid] <= nums[end]) {
end = mid;
} else if (nums[mid] == target) {
return mid;
} else {
start = mid;
}
} else {
if (nums[mid] > nums[end] || nums[mid] < target) {
start = mid;
} else if (nums[mid] == target) {
return mid;
} else {
end = mid;
}
}
}

if (nums[start] == target) {
return start;
}

if (nums[end] == target) {
return end;
}

return -1;
}

搜索旋转排序数组 II

题目来源于 LeetCode 上第 33 号问题:搜索旋转排序数组 II。题目难度为 Medium,目前通过率为 33.9% 。

题目描述

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

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

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false。

示例 1:

输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true

示例 2:

输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false

思考

这道题和前面那道题相比,只是增加了一个条件,就是数组中允许出现重复的元素。

可能很多人纠结的地方会是在首尾两个指针上,允许重复说明,这两个指针上的元素也会是重复的,就比如我们当前的二分中点的元素值是 x,然后你对比发现首尾两个元素的值也都是 x,那么你怎么确定这个数是在前区间还是后区间?

我的做法是用循环去做判断,如果二分中点元素的值和尾指针元素的值相同,那么我就会向后移动这个二分中点,如果发现移到某一点,这一点并不是尾指针,那么说明这个二分中点在前区间,如果移到了尾指针处,说明这个点在后区间,其他照旧。

这里说明一点,这道题的最坏情况的时间复杂度会退化到 O(n) 的,也就是说数组里面的元素全部相同,但是我们要找的元素不在数组内,比如 [2,2,2,2,2,2,2],我们要找的数是 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
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return false;
}

int start = 0, end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;

if (nums[mid] == nums[end]) {
int tmp = mid;
while (tmp < end && nums[tmp] == nums[end]) {
tmp++;
}
//去除重复的多余项
if (nums[tmp] == nums[end]) { //3 1 1 2 2 2 2
end = mid;
} else { // 5 5 5 5 0 1 5
start = mid;
}

continue;
}

if (target < nums[end]) {
if (nums[mid] > nums[end] || nums[mid] <= target) {
start = mid;
} else {
end = mid;
}
} else if (target == nums[end]) {
return true;
} else {
if (nums[mid] < nums[end] || nums[mid] >= target) {
end = mid;
} else {
start = mid;
}
}
}

if (nums[start] == target || nums[end] == target) {
return true;
}

return false;
}

游刃有余:按值二分

这一类题目在二分里面算是难题了。题目通常不会要你在数组中去做查找,往往是让你去使用二分去逼近一个答案,这个答案往往也是近似的。

x的平方根

题目来源于 LeetCode 上第 69 号问题:x 的平方根。题目难度为 Medium,目前通过率为 36.1% 。

题目分析

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:

1
2
输入: 4
输出: 2

示例 2:

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

思考

如果输入参数是任意的浮点数,可以想想怎么做。那么这个时候我们就需要一个精确度,然后我们逐渐去逼近答案。

但是这里有一个 tricky 的地方就是,如果输入的这个数是小于 1 的话,你得把 start 和 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
public double mySqrtComp(double x) {
if (x == 0.0 || x == 1.0) {
return x;
}

double left = 0.0, right = x, eps = 1e-7;

if (x < 1.0) {
left = x;
right = 1.0;
}

while (Math.abs(right - left) > eps) {
double mid = left + (right - left) / 2.0;

if (Math.abs(mid * mid - x) < eps) {
return mid;
} else if (mid * mid < x) {
left = mid;
} else {
right = mid;
}
}

return left;
}

返璞归真:二分其他题型

乘法表中第 k 小的数

题目来源于 LeetCode 上第 668 号问题:乘法表中第 k 小的数。题目难度为 Hard,目前通过率为 34.4% 。

题目描述

几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第 k 小的数字吗?

给定高度 m 、宽度 n 的一张 m * n的乘法表,以及正整数 k,你需要返回表中第 k 小的数字。

例 1:

1
2
3
4
5
6
7
输入: m = 3, n = 3, k = 5
输出: 3
解释: 乘法表:
1 2 3
2 4 6
3 6 9
5小的数字是 3 (1, 2, 2, 3, 3).

例 2:

1
2
3
4
5
6
输入: m = 2, n = 3, k = 6
输出: 6
解释: 乘法表:
1 2 3
2 4 6
6小的数字是 6 (1, 2, 2, 3, 4, 6).

注意:

1
2
m 和 n 的范围在 [1, 30000] 之间。
k 的范围在 [1, m * n] 之间。

思考

在一个乘法表里面寻找第 K 小的元素。

这道题自我感觉是非常 tricky 的一道题,一开始想很难想到可以用二分,其二分的思路类似按值二分,但是还是不一样,至少说这道题最后是可以得到一个确定的解的。

思路大概是,给定乘法表中,最后一个元素是最大的,其值是 mn,第一个元素是最小的,其值是 1,由此我们就可以确认前后指针,然后我们每次都用二分中点去判断,看看矩阵中有多少个数是小于这个值的,如果说矩阵中有超过 K 个数小于这个值,那说明这个二分中点大了,要移动后指针,反之,缩短前指针。

很难理解的原因是,我们可能会认为二分最后得到的答案有可能不在乘法矩阵中,但这个疑点其实是可以利用二分的性质来解释的,二分就是不断趋近于最后的答案的过程,而且这里我们是二分整数,你可以把这道题想象成找元素在数组中最先出现的位置。

举个例子,假如说乘法表中第 K 个出现的元素是 10,你会发现 11 也可以,但是 11 并不在乘法表中,在二分的过程中,我们找到 11 了,但是我们并不会直接返回结果,我们会把后指针移到 11 的位置,然后继续在 11 之前的区间查找。

直到二分把区间缩小到只剩下 1 到 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
28
29
30
31
public int findKthNumber(int m, int n, int k) {
int start = 1, end = m * n;
while (start + 1 < end) {
int mid = start + (end - start) / 2;

if (count(mid, m, n, k)) {
end = mid;
} else {
start = mid;
}
}

if (count(start, m, n, k)) {
return start;
}

return end;
}

private boolean count(int mid, int m, int n, int k) {
int res = 0;
for (int i = 1; i <= m; ++i) {
if (mid / i == 0) {
break;
}

res += Math.min(mid / i, n);
}

return res >= k;
}

未完待续