@@ -167,11 +167,11 @@ int binarySearch(vector<int>& nums, int target){
167
167
int mid = left + ((right - left) >> 1);
168
168
if(nums[ mid] == target){ return mid; }
169
169
// 搜索区间变为 [ mid+1, right]
170
- else if(nums[ mid] < target)
170
+ else if(nums[ mid] < target)
171
171
left = mid + 1;
172
172
// 搜索区间变为 [ left, mid - 1]
173
- else
174
- right = mid - 1;
173
+ else
174
+ right = mid - 1;
175
175
}
176
176
return -1;
177
177
}
@@ -272,7 +272,6 @@ function binarySearchLeft(nums, target) {
272
272
273
273
##### C++
274
274
275
-
276
275
``` cpp
277
276
int binarySearchLeft (vector<int >& nums, int target) {
278
277
// 搜索区间为 [ left, right]
@@ -552,24 +551,22 @@ LeetCode 有原题 [33. 搜索旋转排序数组](https://leetcode-cn.com/proble
552
551
553
552
- 我们可以先找出 mid,然后根据 mid 来判断,mid 是在有序的部分还是无序的部分
554
553
555
- 假如 mid 小于 start,则 mid 一定在右边有序部分。
556
- 假如 mid 大于 start,则 mid 一定在左边有序部分。
554
+ 假如 mid 小于 start,则 mid 一定在右边有序部分,即 [ mid,end] 部分有序。假如 mid 大于 start,则 mid 一定在左边有序部分,即 [ start,mid] 部分有序。** 这是这类题目的突破口。**
557
555
558
556
> 注意我没有考虑等号,之后我会讲。
559
557
560
- - 然后我们继续判断 target 在哪一部分, 我们就可以舍弃另一部分了
558
+ - 然后我们继续判断 target 在哪一部分, 就可以舍弃另一部分了。
561
559
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 实现), 反之亦然。
565
562
566
563
我们以([ 6,7,8,1,2,3,4,5] , 4)为例讲解一下:
567
564
568
565
![ ] ( https://tva1.sinaimg.cn/large/007S8ZIlly1gh9ahf86uyj30if0b0t9w.jpg )
569
566
570
567
![ ] ( https://tva1.sinaimg.cn/large/007S8ZIlly1gh9ahoznqjj30gx0i2wgb.jpg )
571
568
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 了。
573
570
574
571
##### 代码(Python)
575
572
0 commit comments