1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include <iostream>
#include <vector>
int binarysear(std::vector<int> &nums, int target){
int left = 0;
int right = nums.size();
while(left <= right){
int mid = left+(right - left) / 2 ;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid +1;
else if (nums[mid] > target)
right = mid -1;
}
return -1;
}
int main(int argc, char *argv[])
{
std::vector<int> arr = {1,2,2,2,3};
int rest = binarysear(arr, 2);
std::cout<<rest<<std::endl;
return 0;
}
|
此算法的缺陷：
比如说给你有序数组 nums = [1,2,2,2,3]，target 为 2，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。
寻找左侧边界的二分搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int leftbinarysear(std::vector<int> nums, int target){
int left = 0;
int right = nums.size() - 1;
while(left <= right){
int mid = left+(right - left) / 2 ;
if(nums[mid] > target)
right = mid - 1;
else if (nums[mid] < target)
left = mid +1;
else if (nums[mid] == target)
right = mid -1;
}
if(left >= nums.size() || nums[left] != target){
return -1;
}
return left;
}
|
寻找右侧边界的二分搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int rightbinarysear(std::vector<int> nums, int target){
int left = 0;
int right = nums.size() - 1;
while(left <= right){
int mid = left+(right - left) / 2 ;
if(nums[mid] > target)
right = mid - 1;
else if (nums[mid] < target)
left = mid +1;
else if (nums[mid] == target)
left = mid + 1;
}
if(right < 0 || nums[right] != target){
return -1;
}
return right;
}
|
note：
常规做法很简单就是：nums[mid] == target 时，左侧 left = mid +1 右侧 right = mid + 1。
将「搜索区间」全都统一成两端都闭，好记，只要稍改 nums[mid] == target 条件处的代码和返回的逻辑即可。
即在左侧做二分搜索时，只需在 nums[mid] == target 时进行 right = mid -1持续向左侧收紧。
在右侧做二分搜索时，只需在 nums[mid] = target 时进行 left = mid +1 持续向右侧收紧。
LeetCode
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
Follow up: Could you write an algorithm with O(log n) runtime complexity?
Example 1:
1
2
| Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
|
Example 2:
1
2
| Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
|
Example 3:
1
2
| Input: nums = [], target = 0
Output: [-1,-1]
|
Constraints:
0 <= nums.length <= 105-109 <= nums[i] <= 109nums is a non-decreasing array.-109 <= target <= 109
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res;
res.push_back(leftBinSearch(nums, target));
res.push_back(rightBinSearch(nums, target));
return res;
}
int leftBinSearch(vector<int>& nums, int target){
int left = 0;
int right = nums.size() - 1;
while(left <= right){
int mid = left + (right - left)/2;
if(target > nums[mid]){
left = mid + 1;
}
else if (target < nums[mid]){
right = mid - 1;
}
else if (nums[mid] == target){
right = mid - 1;
}
}
if(left >= nums.size() || nums[left] != target){
return -1;
}
return left;
}
int rightBinSearch(vector<int>& nums, int target){
int left = 0;
int right = nums.size() - 1;
while(left <= right){
int mid = left + (right - left)/2;
if(target > nums[mid]){
left = mid + 1;
}
else if (target < nums[mid]){
right = mid - 1;
}
else if (nums[mid] == target){
left = mid + 1;
}
}
if(right < 0 || nums[right] != target){
return -1;
}
return right;
}
};
|
