Skip to content

Commit 289fb9f

Browse files
chienmychienmy
committed
add binary_search
1 parent 6403581 commit 289fb9f

File tree

2 files changed

+305
-0
lines changed

2 files changed

+305
-0
lines changed

‎basic_algorithm/binary_search.md

Lines changed: 305 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,305 @@
1+
# 二分搜索
2+
3+
## 简介
4+
5+
给一个**有序数组**和目标值，找第一次/最后一次/任何一次出现的索引，如果没有出现返回-1
6+
7+
模板四点要素
8+
9+
- 1、初始化：start=0、end=len-1
10+
- 2、循环退出条件：start + 1 < end
11+
- 3、比较中点和目标值：A[mid] ==、 <、> target
12+
- 4、判断最后两个元素是否符合：A[start]、A[end] ? target
13+
14+
时间复杂度 O(logn)，使用场景一般是有序数组的查找
15+
16+
### 典型示例
17+
18+
> [704. 二分查找](https://leetcode-cn.com/problems/binary-search/)
19+
>
20+
> 给定一个  n  个元素有序的（升序）整型数组  nums 和一个目标值  target  ，写一个函数搜索  nums  中的 target，如果目标值存在返回下标，否则返回 -1。
21+
22+
```java
23+
// 二分搜索最常用模板
24+
public int search(int[] nums, int target) {
25+
// 1、初始化left、right
26+
int left = 0;
27+
int right = nums.length - 1;
28+
// 2、处理for循环
29+
while (right - left > 1) {
30+
int mid = left + (right - left) / 2;
31+
// 3、比较nums[mid]和target值
32+
if (nums[mid] == target) {
33+
return mid;
34+
} else if (nums[mid] < target) {
35+
left = mid;
36+
} else {
37+
right = mid;
38+
}
39+
}
40+
// 4、最后剩下两个元素，手动判断
41+
if (nums[left] == target) {
42+
return left;
43+
} else if (nums[right] == target) {
44+
return right;
45+
} else {
46+
return -1;
47+
}
48+
}
49+
```
50+
51+
### 模板
52+
53+
大部分二分查找类的题目都可以用这个模板，然后做一点特殊逻辑即可
54+
55+
另外二分查找还有一些其他模板如下图，大部分场景模板#3 都能解决问题，而且还能找第一次/最后一次出现的位置，应用更加广泛
56+
57+
![binary_search_template](https://img.fuiboom.com/img/binary_search_template.png)
58+
59+
所以用模板#3 就对了，详细的对比可以这边文章介绍：[二分搜索模板](https://leetcode-cn.com/explore/learn/card/binary-search/212/template-analysis/847/)
60+
61+
如果是最简单的二分搜索，不需要找第一个、最后一个位置、或者是没有重复元素，可以使用模板#1，代码更简洁常见题目
62+
63+
## 常见题目
64+
65+
### 搜索插入位置
66+
67+
> [35. 搜索插入位置](https://leetcode-cn.com/problems/search-insert-position/)
68+
>
69+
> 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
70+
71+
```java
72+
public int searchInsert(int[] nums, int target) {
73+
// 思路：找到第一个 >= target 的元素位置
74+
int left = 0;
75+
int right = nums.length - 1;
76+
while (right - left > 1) {
77+
int mid = left + (right - left) / 2;
78+
if (nums[mid] == target) {
79+
return mid;
80+
} else if (nums[mid] < target) {
81+
left = mid;
82+
} else {
83+
right = mid;
84+
}
85+
}
86+
if (nums[left] >= target) {
87+
return left;
88+
} else if (nums[left] < target && target <= nums[right]) {
89+
return left + 1;
90+
} else {
91+
// 目标值比所有值都大
92+
return right + 1;
93+
}
94+
}
95+
```
96+
97+
### 搜索二维矩阵
98+
99+
> [74. 搜索二维矩阵](https://leetcode-cn.com/problems/search-a-2d-matrix/)
100+
>
101+
> 编写一个高效的算法来判断  m x n  矩阵中，是否存在一个目标值。该矩阵具有如下特性：
102+
>
103+
> - 每行中的整数从左到右按升序排列。
104+
> - 每行的第一个整数大于前一行的最后一个整数。
105+
106+
```java
107+
public boolean searchMatrix(int[][] matrix, int target) {
108+
// 思路：将2维数组转为1维数组 进行二分搜索
109+
if (matrix.length == 0 || matrix[0].length == 0) {
110+
return false;
111+
}
112+
int row = matrix.length;
113+
int col = matrix[0].length;
114+
int left = 0;
115+
int right = row * col - 1;
116+
while (right - left > 1) {
117+
int mid = left + (right - left) / 2;
118+
// 获取2维数组对应值
119+
int val = matrix[mid/col][mid%col];
120+
if (val < target) {
121+
left = mid;
122+
} else if (val > target) {
123+
right = mid;
124+
} else {
125+
return true;
126+
}
127+
}
128+
if (matrix[left/col][left%col] == target || matrix[right/col][right%col] == target) {
129+
return true;
130+
}
131+
return false;
132+
}
133+
```
134+
135+
### 寻找旋转排序数组中的最小值
136+
137+
> [153. 寻找旋转排序数组中的最小值](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/)
138+
>
139+
> 假设按照升序排序的数组在预先未知的某个点上进行了旋转( 例如，数组  [0,1,2,4,5,6,7] 可能变为  [4,5,6,7,0,1,2] )。
140+
> 请找出其中最小的元素。
141+
142+
```java
143+
public int findMin(int[] nums) {
144+
// 思路：最后一个值作为target，然后往左移动，最后比较start、end的值
145+
if (nums.length == 0) {
146+
return -1;
147+
}
148+
int left = 0;
149+
int right = nums.length - 1;
150+
while (right - left > 1) {
151+
int mid = left + (right - left) / 2;
152+
// 最后一个元素值为target
153+
if (nums[mid] > nums[right]) {
154+
left = mid;
155+
} else {
156+
right = mid;
157+
}
158+
}
159+
return Math.min(nums[left], nums[right]);
160+
}
161+
```
162+
163+
### 寻找旋转排序数组中的最小值 II
164+
165+
> [154. 寻找旋转排序数组中的最小值 II](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/)
166+
>
167+
> 假设按照升序排序的数组在预先未知的某个点上进行了旋转
168+
> ( 例如，数组  [0,1,2,4,5,6,7] 可能变为  [4,5,6,7,0,1,2] )。
169+
> 请找出其中最小的元素。(包含重复元素)
170+
171+
```java
172+
public int findMin(int[] nums) {
173+
// 思路：跳过重复元素，mid值和end值比较，分为两种情况进行处理
174+
if (nums.length == 0) {
175+
return -1;
176+
}
177+
int left = 0;
178+
int right = nums.length - 1;
179+
while (right - left > 1) {
180+
// 去除重复元素
181+
while (left < right && nums[right] == nums[right - 1]) {
182+
right--;
183+
}
184+
while (left < right && nums[left] == nums[left + 1]) {
185+
left++;
186+
}
187+
int mid = left + (right - left) / 2;
188+
// 中间元素和最后一个元素比较（判断中间点落在左边上升区，还是右边上升区）
189+
if (nums[mid] > nums[right]) {
190+
left = mid;
191+
} else {
192+
right = mid;
193+
}
194+
}
195+
return Math.min(nums[left], nums[right]);
196+
}
197+
```
198+
199+
### 搜索旋转排序数组
200+
201+
> [33. 搜索旋转排序数组](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/)
202+
>
203+
> 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
204+
> ( 例如，数组  [0,1,2,4,5,6,7]  可能变为  [4,5,6,7,0,1,2] )。
205+
> 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回  -1 。
206+
> 你可以假设数组中不存在重复的元素。
207+
208+
```java
209+
public int search(int[] nums, int target) {
210+
// 思路：四种情况判断
211+
if (nums.length == 0) {
212+
return -1;
213+
}
214+
int left = 0;
215+
int right = nums.length - 1;
216+
while (right - left > 1) {
217+
int mid = left + (right - left) / 2;
218+
// 相等直接返回
219+
if (nums[mid] == target) {
220+
return mid;
221+
}
222+
// 判断在哪个区间，可能分为四种情况
223+
if (nums[left] < nums[mid]) {
224+
if (nums[left] <= target && target <= nums[mid]) {
225+
right = mid;
226+
} else {
227+
left = mid;
228+
}
229+
} else if (nums[right] > nums[mid]) {
230+
if (nums[right] >= target && target >= nums[mid]) {
231+
left = mid;
232+
} else {
233+
right = mid;
234+
}
235+
}
236+
}
237+
if (nums[left] == target) {
238+
return left;
239+
} else if (nums[right] == target) {
240+
return right;
241+
}
242+
return -1;
243+
}
244+
```
245+
246+
注意点
247+
248+
> 面试时，可以直接画图进行辅助说明，空讲很容易让大家都比较蒙圈
249+
250+
### 搜索旋转排序数组 II
251+
252+
> [81. 搜索旋转排序数组 II](https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/)
253+
>
254+
> 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
255+
> ( 例如，数组  [0,0,1,2,2,5,6]  可能变为  [2,5,6,0,0,1,2] )。
256+
> 编写一个函数来判断给定的目标值是否存在于数组中。若存在返回  true，否则返回  false。(包含重复元素)
257+
258+
```java
259+
public boolean search(int[] nums, int target) {
260+
// 思路：四种情况判断
261+
if (nums.length == 0) {
262+
return false;
263+
}
264+
int left = 0;
265+
int right = nums.length - 1;
266+
while (right - left > 1) {
267+
// 去除重复元素
268+
while (left < right && nums[right] == nums[right - 1]) {
269+
right--;
270+
}
271+
while (left < right && nums[left] == nums[left + 1]) {
272+
left++;
273+
}
274+
int mid = left + (right - left) / 2;
275+
// 相等直接返回
276+
if (nums[mid] == target) {
277+
return true;
278+
}
279+
// 判断在哪个区间，可能分为四种情况
280+
if (nums[left] < nums[mid]) {
281+
if (nums[left] <= target && target <= nums[mid]) {
282+
right = mid;
283+
} else {
284+
left = mid;
285+
}
286+
} else if (nums[right] > nums[mid]) {
287+
if (nums[right] >= target && target >= nums[mid]) {
288+
left = mid;
289+
} else {
290+
right = mid;
291+
}
292+
}
293+
}
294+
return (nums[left] == target || nums[right] == target);
295+
}
296+
```
297+
298+
## 总结
299+
300+
二分搜索核心四点要素（必背&理解）
301+
302+
- 1、初始化：start=0、end=len-1
303+
- 2、循环退出条件：start + 1 < end
304+
- 3、比较中点和目标值：A[mid] ==、 <、> target
305+
- 4、判断最后两个元素是否符合：A[start]、A[end] ? target

‎images/binary_search_template.png

36.2 KB
Loading

0 commit comments

Comments
 (0)