34. Search for a Range
Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
题解：
输入一个包含重复元素的有序的数组 nums 和目标数target，输出目标数在nums 上的对应区间 result = [getBegin, getEnd]；如果 target 不在 nums 中，输出 result = [-1, -1]；
输入的是有序数组，优先考虑二分查找：https://www.jianshu.com/p/5ca633157c0f
查找 target 在无重复 nums 中的对应位置：https://www.jianshu.com/p/37ae38bdd3a5
这道题我们查找 target 在nums 中的对应位置是不够的，需要增加额外的条件来获取target 在nums 中的区间左端点的对应位置和区间右端点的对应位置；
在满足 target == nums[mid] 的这个大前提下：
如果 nums[mid] 是区间左端点，有两种情况：
- nums[mid] 是数组 nums 的第一个元素（mid == 0）；
- nums[mid] 比它左边的元素值大（nums[mid] > nums[mid - 1]）；
如果 nums[mid] 是区间右端点，有两种情况：
- nums[mid] 是数组 nums 的最后一个元素（mid == nums.size() - 1）；
- nums[mid] 比它右边的元素值小（nums[mid] < nums[mid - 1]）；
那如果 nums[mid] 既不是区间左端点，也不是区间右端点呢要怎么处理呢？
我们可以用两个函数分别用于获取左端点和获取右端点；
- 在获取左端点的函数 getBegin() 中：
在满足 target == nums[mid] 的这个大前提下：
如果 nums[mid] 不是区间左端点：
说明左端点在 nums[mid] 的左侧，所以我们只需要取 nums[mid] 的前半段（ end = mid - 1），然后继续查找左端点位置即可； - 在获取左端点的函数 getBegin() 中：
在满足 target == nums[mid] 的这个大前提下：
如果 nums[mid] 不是区间右端点：
说明右端点在 nums[mid] 的右侧，所以我们只需要取 nums[mid] 的后半段（ begin = mid + 1），然后继续查找右端点位置即可；
My Solution(C/C++)
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> searchRange(vector<int> &nums, int target) {
vector<int> result;
//int begin = 0;
//int end = nums.size() - 1;
result.push_back(getBegin(nums, target));
result.push_back(getEnd(nums, target));
return result;
}
private:
int getBegin(vector<int> &nums, int target) {
int begin = 0;
int end = nums.size() - 1;
while (begin <= end) {
int mid = (begin + end) / 2;
if (target < nums[mid]) {
end = mid - 1;
}
else if (target > nums[mid]) {
begin = mid + 1;
}
else if (target == nums[mid]) {
if (mid == 0 || target > nums[mid - 1]) {
return mid;
}
end = mid - 1;
}
}
return -1;
}
int getEnd(vector<int> &nums, int target) {
int begin = 0;
int end = nums.size() - 1;
while (begin <= end) {
int mid = (begin + end) / 2;
if (target < nums[mid]) {
end = mid - 1;
}
else if (target > nums[mid]) {
begin = mid + 1;
}
else if (target == nums[mid]) {
if (mid == nums.size() - 1 || target < nums[mid + 1]) {
return mid;
}
begin = mid + 1;
}
}
return -1;
}
};
int main() {
vector<int> nums;
nums.push_back(5);
nums.push_back(7);
nums.push_back(7);
nums.push_back(8);
nums.push_back(8);
nums.push_back(10);
Solution s;
vector<int> result;
result = s.searchRange(nums, 8);
for (int i = 0; i < result.size(); i++) {
printf("%d ", result[i]);
}
return 0;
}
结果
3 4
My Solution(Python)
class Solution:
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# begin, end, left, right = 0, len(nums) - 1, -1, -1
left = self.binary_get_left(0, len(nums) - 1, -1, nums, target)
right = self.binary_get_right(0, len(nums) - 1, -1, nums, target)
return [left, right]
def binary_get_left(self, begin, end, left, nums, target):
while begin <= end:
mid = (begin + end) // 2
if nums[mid] == target:
if mid == 0 or nums[mid - 1] != target:
left = mid
# begin = mid + 1
# else:
end = mid - 1
# if mid == len(nums) - 1 or nums[mid + 1] != target:
# right = mid
# end = mid - 1
elif nums[mid] < target:
begin = mid + 1
else:
end = mid - 1
return left
def binary_get_right(self, begin, end, right, nums, target):
while begin <= end:
mid = (begin + end) // 2
if nums[mid] == target:
# if mid == 0 or nums[mid - 1] != target:
# left = mid
# begin = mid + 1
# else:
# end = mid - 1
if mid == len(nums) - 1 or nums[mid + 1] != target:
right = mid
# end = mid - 1
# else:
begin = mid + 1
elif nums[mid] < target:
begin = mid + 1
else:
end = mid - 1
return right
Reference:
class Solution:
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
start = self.firstGreaterEqaul(nums, target)
if start==len(nums) or nums[start]!=target:
return [-1, -1]
return [start, self.firstGreaterEqaul(nums, target+1)-1]
def firstGreaterEqaul(self, nums, target):
lo, hi = 0, len(nums)
while lo<hi:
mid = (hi+lo)//2
if nums[mid]<target:
lo = mid + 1
else:
hi = mid
return lo
