Skip to content

Commit e6e5062

Browse files
author
lucifer
committed
fix: 文案优化
1 parent 3b86dae commit e6e5062

File tree

1 file changed

+8
-11
lines changed

1 file changed

+8
-11
lines changed

91/binary-search.md

Lines changed: 8 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -167,11 +167,11 @@ int binarySearch(vector<int>& nums, int target){
167167
int mid = left + ((right - left) >> 1);
168168
if(nums[mid] == target){ return mid; }
169169
// 搜索区间变为 [mid+1, right]
170-
else if(nums[mid] < target)
170+
else if(nums[mid] < target)
171171
left = mid + 1;
172172
// 搜索区间变为 [left, mid - 1]
173-
else
174-
right = mid - 1;
173+
else
174+
right = mid - 1;
175175
}
176176
return -1;
177177
}
@@ -272,7 +272,6 @@ function binarySearchLeft(nums, target) {
272272

273273
##### C++
274274

275-
276275
```cpp
277276
int binarySearchLeft(vector<int>& nums, int target) {
278277
// 搜索区间为 [left, right]
@@ -552,24 +551,22 @@ LeetCode 有原题 [33. 搜索旋转排序数组](https://leetcode-cn.com/proble
552551

553552
- 我们可以先找出 mid,然后根据 mid 来判断,mid 是在有序的部分还是无序的部分
554553

555-
假如 mid 小于 start,则 mid 一定在右边有序部分。
556-
假如 mid 大于 start,则 mid 一定在左边有序部分。
554+
假如 mid 小于 start,则 mid 一定在右边有序部分,即 [mid,end] 部分有序。假如 mid 大于 start,则 mid 一定在左边有序部分,即 [start,mid]部分有序。**这是这类题目的突破口。**
557555

558556
> 注意我没有考虑等号,之后我会讲。
559557
560-
- 然后我们继续判断 target 在哪一部分, 我们就可以舍弃另一部分了
558+
- 然后我们继续判断 target 在哪一部分, 就可以舍弃另一部分了。
561559

562-
我们只需要比较 target 和有序部分的边界关系就行了。 比如 mid 在右侧有序部分,即[mid, end]
563-
那么我们只需要判断 target >= mid && target <= end 就能知道 target 在右侧有序部分,我们就
564-
可以舍弃左边部分了(start = mid + 1), 反之亦然。
560+
也就是说只需要比较 target 和**有序部分**的边界关系就行了。 比如 mid 在右侧有序部分,即[mid,end] 有序。那么我们只需要判断 target >= mid && target <= end 就能知道 target 在右侧有序部分,我们就
561+
可以舍弃左边部分了(通过 start = mid + 1 实现), 反之亦然。
565562

566563
我们以([6,7,8,1,2,3,4,5], 4)为例讲解一下:
567564

568565
![](https://tva1.sinaimg.cn/large/007S8ZIlly1gh9ahf86uyj30if0b0t9w.jpg)
569566

570567
![](https://tva1.sinaimg.cn/large/007S8ZIlly1gh9ahoznqjj30gx0i2wgb.jpg)
571568

572-
接下来,我们考虑重复元素的问题。就会发生 nums[mid] == nums[start] 了,比如 30333 。这个时候,可以选择 l 右移一位。有的同学会担心”会不会错失目标元素?“。其实这个担心是多余的,前面我们已经介绍了”搜索区间“。由于搜索区间同时包含 l 和 mid ,因此去除一个 l ,我们还有 mid。假如 3 是我们要找的元素, 这样进行下去绝对不会错过,而是收缩”搜索区间“到一个元素 3 ,我们就可以心安理得地返回 3 了。
569+
接下来,我们考虑重复元素的问题。如果存在重复数字,就可能会发生 nums[mid] == nums[start] 了,比如 30333 。这个时候可以选择舍弃左部分,也就是 left 右移一位。的同学会担心”会不会错失目标元素?“。其实这个担心是多余的,前面我们已经介绍了”搜索区间“。由于搜索区间同时包含 l 和 mid ,因此去除一个 l ,我们还有 mid。假如 3 是我们要找的元素, 这样进行下去绝对不会错过,而是收缩”搜索区间“到一个元素 3 ,我们就可以心安理得地返回 3 了。
573570

574571
##### 代码(Python)
575572

0 commit comments

Comments
 (0)