给一个升序数组，找到目标值在数组中的起始和结束位置，时间复杂度为 O(log n)。
e.g.
给定数组 [5, 7, 7, 8, 8, 10] 和目标值 8，返回 [3, 4]。若目标值不在数组中，返回 [-1, -1]。
我使用最死的二分查找，分别搜索起始和结束位置。这种思路也可以使用递归实现。
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> result = {-, -};
int low = , high = nums.size() - ;
while (low <= high) {
// 二分查找使用 mid = (high + low) / 2 可能溢出
int mid = low + ((high - low) >> 1);
if (nums[mid] == target) {
if (result[] == -) {
if (mid == || nums[mid] != nums[mid - ]) {
result[] = mid;
low = , high = nums.size() - ;
}
else
high = mid - ;
} else {
if (mid == nums.size() - || nums[mid] != nums[mid + ]) {
result[] = mid;
break;
}
else
low = mid + ;
}
}
else if (nums[mid] > target)
high = mid - ;
else if (nums[mid] < target)
low = mid + ;
}
return result;
}C++ STL中自带一些使用二分查找实现的算法，
#include <algorithm>
pair<forward_iterator,forward_iterator> equal_range( forward_iterator first, forward_iterator last, const TYPE& val );
pair<forward_iterator,forward_iterator> equal_range( forward_iterator first, forward_iterator last, const TYPE& val, CompFn comp );
函数 equal_range 返回非递减序列 [first, last) 区间中等于 val 的元素区间，返回值是一对迭代器 i 和 j 。i 是 val 可插入的第一个位置（即lower_bound），j 是 val 可插入的最后一个位置（即upper_bound），equal_range 可以被认为是 lower_bound 和 upper_bound 的结合。
（lower_bound 在 [first, last) 区间进行二分查找，返回大于等于 val 的第一个元素位置。如果所有元素都小于 val，则返回 last 的位置。
upper_bound 在 [first, last) 区间进行二分查找，返回大于 val 的第一个元素位置）
因此以下代码可直接得出结果。
vector<int> searchRange(vector<int>& nums, int target) {
auto bounds = equal_range(nums.begin(), nums.end(), target);
if (bounds.first == bounds.second)
return {-, -};
return {bounds.first - nums.begin(), bounds.second - nums.begin() - };
} vector<int> searchRange(vector<int>& nums, int target) {
int lo = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
if (lo == nums.size() || nums[lo] != target)
return {-, -};
int hi = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - ;
return {lo, hi};
}