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,0,nums.size()-1,target); if(ans == -1) return {-1,-1}; //归结根底，vector就是一个数组，可以用{}。 int left = ans,right = ans; while(left > 0 && nums[left-1] == nums[ans]) left--; while(right < nums.size() - 1 && nums[right+1] == 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); } };
还有一个解法：
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int ans = search(nums,0,nums.size()-1,target); if(ans == -1) return {-1,-1}; int left = ans,right = ans; while(left > 0 && nums[left-1] == nums[ans]) left--; while(right < nums.size() - 1 && nums[right+1] == 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() == 0) return -1; while(left + 1 < right){ int mid = left + (right - left)/2; 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 -1; } };
emmm，也可以看官方题解：https://leetcode.com/articles/find-first-and-last-position-element-sorted-array/
转载于:https://www.cnblogs.com/Weixu-Liu/p/10757970.html
