Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Appearance settings

Commit 289fb9f

Browse filesBrowse files
committed
add binary_search
1 parent 6403581 commit 289fb9f
Copy full SHA for 289fb9f

File tree

Expand file treeCollapse file tree

2 files changed

+305
-0
lines changed
Filter options
Expand file treeCollapse file tree

2 files changed

+305
-0
lines changed

‎basic_algorithm/binary_search.md

Copy file name to clipboard
+305Lines 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

Copy file name to clipboard
36.2 KB
Loading

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.