描述：

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 = 8Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6Output: [-1,-1]

思路一：一次Binary Search

先使用二分查找找到和taget相等的起始位置的元素，然后在这个位置向两边扩散找到值相同的范围。

class Solution {public:    vector
     
       searchRange(vector
      
       & nums, int target) {        vector
       
         res(2,-1);        if(nums.size() == 0) return res;        int cau = dichotomy(nums,target);        if(cau == -1) return res;        else{            int i = cau,j = cau;            cout<
        
         <
         
          =0 && nums[i] == target) || (j<=nums.size()-1 && nums[j] == target)){                if(i>=0 && nums[i] == target){                    res[0] = i;                    cout<
          <

& nums, int target){ int low = 0,int high = nums.size() - 1; while(low < high){ int mid = (low + high + 1) / 2; if(nums[mid] == target) return mid; if(nums[mid] < target) low = mid + 1; else high = mid - 1; } return -1; }};

思路二：两3次Binary Search

先根据上述的二分查找，找到起始位置的元素，然后从low开始继续使用一次二分查找找到target+1的位置，然后返回这个位置it - 1，从而找到起始和终止的范围。

class Solution {public:    vector
     
       searchRange(vector
      
       & nums, int target) {        vector
       
         res(2,-1);        if(nums.size() == 0) return res;        int low = dichotomy(nums,target,0);   //找起始元素        cout<
        
         <

& nums, int target, int low){ int high = nums.size(); //核心 while(low < high){ int mid = (low + high ) / 2; if(nums[mid] < target) low = mid + 1; else high = mid; } return low; }};

转载于:https://www.cnblogs.com/ygh1229/p/9726966.html