Given an array of integers nums 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].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
------------------------------------------------------------------------------------
这个题是在leetcode和lintcode 上都有的，只不过题目里面给的参数有些是不同的，需要注意的，不过代码是基本相同的。
用遍历数组的方式可能会TLE，所以用二分更好。
emmm，二分查找也可以用递归方式来写的。当用二分查找方式得到一个不为-1数组下标时，向两边扩展，最终得到一个范围。
C++代码：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int ans = search(nums,,nums.size()-,target);
if(ans == -) return {-,-}; //归结根底，vector就是一个数组，可以用{}。
int left = ans,right = ans;
while(left > && nums[left-] == nums[ans]) left--;
while(right < nums.size() - && nums[right+] == nums[ans]) right++;
return {left,right};
}
int search(vector<int>& nums,int left,int right,int target){
if(left > right) return -;
int mid = left + (right - left)/;
if(nums[mid] == target) return mid;
if(nums[mid] > target) return search(nums,,mid-,target);
else return search(nums,mid+,right,target);
}
};
还有一个解法：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int ans = search(nums,,nums.size()-,target);
if(ans == -) return {-,-};
int left = ans,right = ans;
while(left > && nums[left-] == nums[ans]) left--;
while(right < nums.size() - && nums[right+] == nums[ans]) right++;
return {left,right};
}
int search(vector<int>& nums,int left,int right,int target){
// if(left > right) return -1;
// int mid = left + (right - left)/2;
// if(nums[mid] == target) return mid;
// if(nums[mid] > target) return search(nums,0,mid-1,target);
// else return search(nums,mid+1,right,target);
if(nums.size() == ) return -;
while(left + < right){
int mid = left + (right - left)/;
if(nums[mid] > target) right = mid;
else if(nums[mid] < target) left = mid;
else return mid;
}
if(nums[left] == target) return left;
if(nums[right] == target) return right;
return -;
}
};
emmm，也可以看官方题解：https://leetcode.com/articles/find-first-and-last-position-element-sorted-array/