Skip to content

Commit cfa0ed9

Browse files
da183da183
committed
代码提交
1 parent 2cc7517 commit cfa0ed9

File tree

4 files changed

+378
-476
lines changed

4 files changed

+378
-476
lines changed

‎basic_algorithm/binary_search.md‎

Lines changed: 141 additions & 149 deletions
Original file line numberDiff line numberDiff line change
@@ -19,32 +19,32 @@
1919

2020
> 给定一个  n  个元素有序的（升序）整型数组  nums 和一个目标值  target  ，写一个函数搜索  nums  中的 target，如果目标值存在返回下标，否则返回 -1。
2121
22-
```go
22+
```c++
2323
// 二分搜索最常用模板
24-
func search(nums []int, target int) int {
24+
int search(vector<int> &nums, int target) {
2525
// 1、初始化start、end
26-
start := 0
27-
end := len(nums) - 1
26+
auto start = 0;
27+
auto end = nums.size() - 1;
2828
// 2、处理for循环
29-
for start+1 < end {
30-
mid := start + (end-start)/2
29+
while (start + 1 < end) {
30+
auto mid = start + (end - start) / 2;
3131
// 3、比较a[mid]和target值
32-
if nums[mid] == target {
33-
end = mid
34-
} else if nums[mid] < target {
35-
start = mid
36-
} else if nums[mid] > target {
37-
end = mid
32+
if (nums[mid] == target) {
33+
return mid;
34+
} else if (nums[mid] < target) {
35+
start = mid;
36+
} else {
37+
end = mid;
3838
}
3939
}
4040
// 4、最后剩下两个元素，手动判断
41-
if nums[start] == target {
42-
return start
41+
if (nums[start] == target) {
42+
return start;
4343
}
44-
if nums[end] == target {
45-
return end
44+
if (nums[end] == target) {
45+
return end;
4646
}
47-
return -1
47+
return -1;
4848
}
4949
```
5050
@@ -58,24 +58,24 @@ func search(nums []int, target int) int {
5858
5959
如果是最简单的二分搜索，不需要找第一个、最后一个位置、或者是没有重复元素，可以使用模板#1，代码更简洁
6060
61-
```go
61+
```c++
6262
// 无重复元素搜索时，更方便
63-
func search(nums []int, target int) int {
64-
start := 0
65-
end := len(nums) - 1
66-
for start <= end {
67-
mid := start + (end-start)/2
68-
if nums[mid] == target {
69-
return mid
70-
} else if nums[mid] < target {
71-
start = mid+1
72-
} else if nums[mid] > target {
73-
end = mid-1
63+
int search(vector<int> &nums, int target) {
64+
auto start = 0;
65+
auto end = nums.size() - 1;
66+
while (start <= end) {
67+
auto mid = start + (end - start) / 2;
68+
if (nums[mid] == target) {
69+
return mid;
70+
} else if (nums[mid] < target) {
71+
start = mid + 1;
72+
} else {
73+
end = mid - 1;
7474
}
7575
}
7676
// 如果找不到，start 是第一个大于target的索引
7777
// 如果在B+树结构里面二分搜索，可以return start
78-
// 这样可以继续向子节点搜索，如：node:=node.Children[start]
78+
// 这样可以继续向子节点搜索，如：node = node.Children[start]
7979
return -1
8080
}
8181
```
@@ -89,90 +89,80 @@ func search(nums []int, target int) int {
8989
9090
思路：核心点就是找第一个 target 的索引，和最后一个 target 的索引，所以用两次二分搜索分别找第一次和最后一次的位置
9191

92-
```go
93-
func searchRange (A []int, target int) []int {
94-
if len(A) == 0 {
95-
return []int{-1, -1}
92+
```c++
93+
// 两次搜索，一次相等时往左一次往右以找出左右边界
94+
vector<int> searchRange(vector<int> &A, int target) {
95+
vector<int> ret = {-1, -1};
96+
if (A.empty()) {
97+
return ret;
9698
}
97-
result := make([]int, 2)
98-
start := 0
99-
end := len(A) - 1
100-
for start+1 < end {
101-
mid := start + (end-start)/2
102-
if A[mid] > target {
103-
end = mid
104-
} else if A[mid] < target {
105-
start = mid
99+
int begin = 0;
100+
int end = A.size();
101+
while (begin + 1 < end) {
102+
auto mid = begin + (end - begin) / 2;
103+
if (A[mid] < target) {
104+
begin = mid;
106105
} else {
107-
// 如果相等，应该继续向左找，就能找到第一个目标值的位置
108-
end = mid
106+
end = mid;
109107
}
110108
}
111-
// 搜索左边的索引
112-
if A[start] == target {
113-
result[0] = start
114-
} else if A[end] == target {
115-
result[0] = end
109+
if (A[begin] == target) {
110+
ret[0] = begin;
111+
} else if (A[end] == target) {
112+
ret[0] = end;
116113
} else {
117-
result[0] = -1
118-
result[1] = -1
119-
return result
114+
return ret;
120115
}
121-
start = 0
122-
end = len(A) - 1
123-
for start+1 < end {
124-
mid := start + (end-start)/2
125-
if A[mid] > target {
126-
end = mid
127-
} else if A[mid] < target {
128-
start = mid
116+
begin = 0;
117+
end = A.size();
118+
while (begin + 1 < end) {
119+
auto mid = begin + (end - begin) / 2;
120+
if (A[mid] <= target) {
121+
begin = mid;
129122
} else {
130-
// 如果相等，应该继续向右找，就能找到最后一个目标值的位置
131-
start = mid
123+
end = mid;
132124
}
133125
}
134-
// 搜索右边的索引
135-
if A[end] == target {
136-
result[1] = end
137-
} else if A[start] == target {
138-
result[1] = start
126+
if (A[begin] == target) {
127+
ret[1] = begin;
128+
} else if (A[end] == target) {
129+
ret[1] = end;
139130
} else {
140-
result[0] = -1
141-
result[1] = -1
142-
return result
131+
return ret;
143132
}
144-
return result
133+
return ret;
145134
}
146135
```
147136
148137
### [search-insert-position](https://leetcode-cn.com/problems/search-insert-position/)
149138
150139
> 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
151140
152-
```go
153-
func searchInsert(nums []int, target int) int {
154-
// 思路：找到第一个 >= target 的元素位置
155-
start := 0
156-
end := len(nums) - 1
157-
for start+1 < end {
158-
mid := start + (end-start)/2
159-
if nums[mid] == target {
160-
// 标记开始位置
161-
start = mid
162-
} else if nums[mid] > target {
163-
end = mid
141+
```c++
142+
int searchInsert(vector<int>& nums, int target) {
143+
if (nums.empty()) {
144+
return 0;
145+
}
146+
147+
int begin = 0;
148+
int end = nums.size() -1;
149+
while (begin + 1 < end) {
150+
auto mid = begin + (end - begin) / 2;
151+
if (nums[mid] == target) {
152+
return mid;
153+
} else if (nums[mid] < target) {
154+
begin = mid;
164155
} else {
165-
start = mid
156+
end = mid;
166157
}
167158
}
168-
if nums[start] >= target {
169-
return start
170-
} else if nums[end] >= target {
171-
return end
172-
} else if nums[end] < target { // 目标值比所有值都大
173-
return end + 1
174-
}
175-
return 0
159+
if (nums[begin] >= target) {
160+
return begin;
161+
} else if (nums[end] >= target) {
162+
return end;
163+
} else {
164+
return end + 1;
165+
}
176166
}
177167
```
178168

@@ -183,32 +173,46 @@ func searchInsert(nums []int, target int) int {
183173
> - 每行中的整数从左到右按升序排列。
184174
> - 每行的第一个整数大于前一行的最后一个整数。
185175
186-
```go
187-
func searchMatrix(matrix [][]int, target int) bool {
188-
// 思路：将2纬数组转为1维数组 进行二分搜索
189-
if len(matrix) == 0 || len(matrix[0]) == 0 {
190-
return false
176+
```c++
177+
bool searchMatrix(vector<vector<int>>& matrix, int target) {
178+
if (matrix.empty() || matrix[0].empty()) {
179+
return false;
191180
}
192-
row := len(matrix)
193-
col := len(matrix[0])
194-
start := 0
195-
end := row*col - 1
196-
for start+1 < end {
197-
mid := start + (end-start)/2
198-
// 获取2纬数组对应值
199-
val := matrix[mid/col][mid%col]
200-
if val > target {
201-
end = mid
202-
} else if val < target {
203-
start = mid
181+
182+
int begin = 0;
183+
int end = matrix.size() - 1;
184+
while (begin + 1 < end) {
185+
auto mid = begin + (end - begin) / 2;
186+
const auto &val = matrix[mid][0];
187+
if (val == target) {
188+
return true;
189+
} else if (val < target) {
190+
begin = mid;
204191
} else {
205-
return true
192+
end = mid;
206193
}
207194
}
208-
if matrix[start/col][start%col] == target || matrix[end/col][end%col] == target{
209-
return true
195+
196+
if (matrix[begin][0] == target || matrix[end][0] == target) {
197+
return true;
210198
}
211-
return false
199+
if (matrix[begin][0] > target || matrix[end][matrix[end].size()- 1] < target) {
200+
return false;
201+
}
202+
const auto &row = matrix[end][0] < target ? matrix[end] : matrix[begin];
203+
begin = 0;
204+
end = row.size() - 1;
205+
while (begin + 1 < end) {
206+
auto mid = begin + (end - begin) / 2;
207+
if (row[mid] == target) {
208+
return true;
209+
} else if (row[mid] < target) {
210+
begin = mid;
211+
} else {
212+
end = mid;
213+
}
214+
}
215+
return row[begin] == target || row[end] == target;
212216
}
213217
```
214218
@@ -217,23 +221,19 @@ func searchMatrix(matrix [][]int, target int) bool {
217221
> 假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
218222
> 你可以通过调用  bool isBadVersion(version)  接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
219223
220-
```go
221-
func firstBadVersion(n int) int {
222-
// 思路：二分搜索
223-
start := 0
224-
end := n
225-
for start+1 < end {
226-
mid := start + (end - start)/2
227-
if isBadVersion(mid) {
228-
end = mid
229-
} else if isBadVersion(mid) == false {
230-
start = mid
224+
```c++
225+
int firstBadVersion(int n) {
226+
int begin = 1;
227+
int end = n;
228+
while (begin + 1 < end) {
229+
auto mid = begin + (end - begin) / 2;
230+
if (isBadVersion(mid)) {
231+
end = mid;
232+
} else {
233+
begin = mid;
231234
}
232235
}
233-
if isBadVersion(start) {
234-
return start
235-
}
236-
return end
236+
return isBadVersion(begin) ? begin : end;
237237
}
238238
```
239239

@@ -242,28 +242,20 @@ func firstBadVersion(n int) int {
242242
> 假设按照升序排序的数组在预先未知的某个点上进行了旋转( 例如，数组  [0,1,2,4,5,6,7] 可能变为  [4,5,6,7,0,1,2] )。
243243
> 请找出其中最小的元素。
244244
245-
```go
246-
func findMin(nums []int) int {
247-
// 思路：/ / 最后一个值作为target，然后往左移动，最后比较start、end的值
248-
if len(nums) == 0 {
249-
return -1
250-
}
251-
start := 0
252-
end := len(nums) - 1
253-
254-
for start+1 < end {
255-
mid := start + (end-start)/2
256-
// 最后一个元素值为target
257-
if nums[mid] <= nums[end] {
258-
end = mid
245+
```c++
246+
int findMin(vector<int>& nums) {
247+
// 最后一个值作为target，以确定是否旋转
248+
int begin = 0;
249+
int end = nums.size() - 1;
250+
while (begin + 1 < end) {
251+
auto mid = begin + (end - begin) / 2;
252+
if (nums[mid] <= nums[end]) {
253+
end = mid;
259254
} else {
260-
start = mid
255+
begin = mid;
261256
}
262257
}
263-
if nums[start] > nums[end] {
264-
return nums[end]
265-
}
266-
return nums[start]
258+
return nums[begin] > nums[end] ? nums[end] : nums[begin];
267259
}
268260
```
269261
@@ -273,7 +265,7 @@ func findMin(nums []int) int {
273265
> ( 例如，数组  [0,1,2,4,5,6,7] 可能变为  [4,5,6,7,0,1,2] )。
274266
> 请找出其中最小的元素。(包含重复元素)
275267
276-
```go
268+
```c++
277269
func findMin(nums []int) int {
278270
// 思路：跳过重复元素，mid值和end值比较，分为两种情况进行处理
279271
if len(nums) == 0 {

0 commit comments

Comments
 (0)