Skip to content

Commit f13d189

Browse files
linwtlinwt
committed
二分查找
1 parent a6c25ea commit f13d189

5 files changed

Lines changed: 94 additions & 10 deletions

File tree

‎leetcode_Java/DoneTitle.txt‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -89,6 +89,7 @@
8989
151. 颠倒字符串中的单词
9090
152. 乘积最大子数组
9191
153. 寻找旋转排序数组中的最小值
92+
154. 寻找旋转排序数组中的最小值 II
9293
155. 最小栈
9394
160. 相交链表
9495
162. 寻找峰值

‎leetcode_Java/DoneType.txt‎

Lines changed: 18 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,7 @@
1010
九、位运算
1111
十、数学
1212
十一、图
13+
十二、二分查找
1314

1415

1516
一、树
@@ -162,20 +163,15 @@
162163
11. 盛最多水的容器（双指针）
163164
15. 三数之和（三指针）
164165
31. 下一个排列（置换）
165-
33. 搜索旋转排序数组（二分查找）
166-
34. 在排序数组中查找元素的第一个和最后一个位置（二分查找）
167166
41. 缺失的第一个正数（置换，排序，集合）
168167
48. 旋转图像（置换）
169168
54. 螺旋矩阵（四指针）
170169
56. 合并区间（二维数组排序）
171170
59. 螺旋矩阵 II（四指针）
172171
75. 颜色分类（单指针，双指针）
173-
81. 搜索旋转排序数组 II（二分查找）
174172
88. 合并两个有序数组（排序，双指针）
175173
128. 最长连续序列（集合，排序）
176174
136. 只出现一次的数字（哈希表，列表，位运算）
177-
153. 寻找旋转排序数组中的最小值（二分查找）
178-
162. 寻找峰值（二分查找）
179175
169. 多数元素（排序，哈希表，投票，计数，分治）
180176
215. 数组中的第K个最大元素（快速排序，堆排序）
181177
238. 除自身以外数组的乘积（前缀和）
@@ -191,7 +187,6 @@
191187
560. 和为 K 的子数组（前缀和，哈希表）
192188
581. 最短无序连续子数组（排序，双指针）
193189
621. 任务调度器（桶填充）
194-
704. 二分查找
195190
867. 转置矩阵（置换）
196191

197192

@@ -221,10 +216,24 @@
221216

222217

223218
十、数学
224-
29. 两数相除（二分查找）
225-
69. x 的平方根（二分查找）
226219
470. 用 Rand7() 实现 Rand10()（拒绝采样）
227220

221+
228222
十一、图
229223
207. 课程表（拓扑排序）
230-
399. 除法求值（并查集）
224+
399. 除法求值（并查集）
225+
226+
227+
十二、二分查找
228+
4. 寻找两个有序数组的中位数（排序，双指针，二分查找）
229+
29. 两数相除（二分查找）
230+
33. 搜索旋转排序数组（二分查找）
231+
34. 在排序数组中查找元素的第一个和最后一个位置（二分查找）
232+
81. 搜索旋转排序数组 II（二分查找）
233+
69. x 的平方根（二分查找）
234+
153. 寻找旋转排序数组中的最小值（二分查找）
235+
154. 寻找旋转排序数组中的最小值 II（二分查找）
236+
162. 寻找峰值（二分查找）
237+
240. 搜索二维矩阵 II（二分查找）
238+
287. 寻找重复数（哈希表，快慢指针，二分查找，位运算）
239+
704. 二分查找

‎leetcode_Java/Solution0153.java‎

Lines changed: 11 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33

44
/*
55
二分查找：二分寻找最小值索引
6-
6+
--------------------------------------------------------------------
77
递增序列：
88
*
99
*
@@ -20,7 +20,17 @@
2020
*
2121
*
2222
*
23+
---------------------------------------------------------------------
24+
例一： 1 2 3 4 5
25+
右排序数组
26+
例二： 3 4 5 | 1 2
27+
左排序数组 右排序数组
2328
29+
1、寻找旋转数组的最小元素即为寻找 右排序数组 的首个元素 nums[x]，称 x 为 旋转点
30+
2、左排序数组任一元素 >= 右排序数组任一元素
31+
3、中值跟右值比较，而不跟左值比较的原因是，右值一定在右排序数组，左值不一定在左排序数组，所以跟左值比较时不能确定中值在哪个排序数组，从而无法确定缩小区间范围
32+
如例一左值在右排序数组，例二左值在左排序数组
33+
---------------------------------------------------------------------
2434
3 4 5 1 2
2535
↑ ↑ ↑
2636
l mid r

‎leetcode_Java/Solution0154.java‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
// 154. 寻找旋转排序数组中的最小值 II
2+
// 剑指offer同题“11. 旋转数组的最小数字”
3+
4+
/*
5+
1、二分查找，比“153. 寻找旋转排序数组中的最小值”多了重复元素
6+
2、当中值等于右值时，无法区分二段性，让右指针左移，去掉一个干扰项
7+
8+
7 0 1 1 1 1 1 2 3 4
9+
↑ ↑ ↑
10+
l m r
11+
=============================
12+
7 0 1 1 1 1 1 2 3 4
13+
↑ ↑ ↑
14+
l m r
15+
=============================
16+
7 0 1 1 1 1 1 2 3 4
17+
↑ ↑ ↑
18+
l m r
19+
=============================
20+
7 0 1 1 1 1 1 2 3 4
21+
↑ ↑
22+
l/m r
23+
=============================
24+
7 0 1 1 1 1 1 2 3 4
25+
↑
26+
l/r
27+
*/
28+
class Solution {
29+
public int findMin(int[] nums) {
30+
int left = 0, right = nums.length - 1;
31+
while (left < right) {
32+
int mid = (left + right) / 2;
33+
if (nums[mid] < nums[right]) {
34+
right = mid;
35+
} else if (nums[mid] > nums[right]) {
36+
left = mid + 1;
37+
} else {
38+
right--;
39+
}
40+
}
41+
return nums[left];
42+
}
43+
}

‎剑指Offer_新版_java/JZ11.java‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,25 @@
11
// 11. 旋转数组的最小数字
2+
// 力扣同题“154. 寻找旋转排序数组中的最小值 II”
3+
4+
/*
5+
二分查找
6+
*/
7+
public class Solution {
8+
public int minNumberInRotateArray(int[] array) {
9+
int left = 0, right = array.length - 1;
10+
while (left < right) {
11+
int mid = (left + right) / 2;
12+
if (array[mid] < array[right]) {
13+
right = mid;
14+
} else if (array[mid] > array[right]) {
15+
left = mid + 1;
16+
} else {
17+
right--;
18+
}
19+
}
20+
return array[left];
21+
}
22+
}
223

324

425
/*

0 commit comments

Comments
 (0)