34. Find First and Last Position of Element in Sorted Array + 二分

题意懒得抄了，大概是：在升序数组中给定整数target，找到第一个和最后一个target的索引，找到返回{index1， index2}，否则返回{-1， -1}；

时间复杂度要求:O(logn)

分析：要求对数时间，又是查找，我们不难想到二分查找。但是有一点，怎么查到第一个和最后一个呢？这困扰了我。

算法：来自leetcode caikehe

1. 使用二分变体，查找target作为index1，再找target+1，作为index2；

2. 对index做判断，如果它未越界且它的对应值等于target则返回{index1， index2-1}；否则，返回{-1， -1}；

源码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        //binary find
        int index1 = binarySearch(nums, target);
        int index2 = binarySearch(nums, target+1) - 1;
        if(index1 < nums.size() && nums[index1] == target)
            return {index1, index2};
        return {-1, -1};
    }
    //二分变体
    int binarySearch(vector<int>& nums, int target)
    {
        int l = 0, r = nums.size()-1;
        while(l <= r)
        {
            int mid = l + (r-l)/2;
            if(nums[mid] < target)
                l = mid + 1;
            else
                r = mid -1;
        }
        return l;
    }
};

一个较为易于理解的算法（时间复杂度可能略高于两次二分）

 1 class Solution {
 2 public:
 3     vector<int> searchRange(vector<int>& nums, int target) {
 4         int len = nums.size();
 5         if(len <= 0)
 6             return {-1, -1};
 7         if(len == 1)
 8             if(nums[0] == target)
 9                 return {0, 0};
10             else
11                 return {-1, -1};
12             
13         
14         int l = 0, r = len-1, mid;
15         while(l <= r)
16         {
17             mid = l + (r-l)/2;
18             if(nums[mid] == target)
19                 break;
20             else if(nums[mid] > target)
21                 r = mid - 1;
22             else
23                 l = mid + 1;
24         }
25         if(nums[mid] != target)
26             return {-1, -1};
27         
28         l = mid, r = mid;
29         while(l >= 0 && nums[l] == nums[mid])
30             l--;
31         while(r < len && nums[r] == nums[mid])
32             r++;
33         return {l+1, r-1};
34     }
35 };