#leetcode刷題之路34-在排序數組中查找元素的第一個和最後一個位置

給定一個按照升序排列的整數數組 nums，和一個目標值 target。找出給定目標值在數組中的開始位置和結束位置。
你的演算法時間複雜度必須是 O(log n) 級別。
如果數組中不存在目標值，返回 [-1, -1]。

示例 1:
輸入: nums = [5,7,7,8,8,10], target = 8
輸出: [3,4]
示例 2:
輸入: nums = [5,7,7,8,8,10], target = 6
輸出: [-1,-1]

思路1：先用二分法找到其中某個target，再向前向後一位一位地找頭和尾；

思路2：改進一下，在第二步找頭和尾時也用二分法；

#include <iostream>
#include <vector>
using namespace std;

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

    int begin=mid;
    int end=mid;

    low=0;
    int m1=mid;
    int m2;
    while(low<=m1)
    {
        m2=(low+m1)/2;
        if(nums[m2]==target&&(m2-1)>=0&&nums[m2-1]<target)
        {
            begin=m2;
            break;
        }
        if(nums[m2]==target&&m2==0)
        {
            begin=m2;
            break;
        }
        if(nums[m2]<target&&(m2+1)<=m1&&nums[m2+1]==target)
        {
            begin=m2+1;
            break;
        }
        if(nums[m2]==target&&(m2-1)>=0&&nums[m2-1]==target) m1=m2-1;
        if(nums[m2]<target&&(m2+1)<nums.size()&&nums[m2+1]<target) low=m2+1;
    }



    high=nums.size()-1;
    if((mid+1)<nums.size()&&nums[mid+1]==target)
    {
        m1=mid+1;
    }
    else
        return {begin,mid};
    while(m1<=high)
    {
        m2=(m1+high)/2;
        if(nums[m2]==target&&(m2+1)<nums.size()&&nums[m2+1]>target)
        {
            end=m2;
            break;
        }
        if(nums[m2]==target&&m2==nums.size()-1)
        {
            end=m2;
            break;
        }
        if(nums[m2]>target&&(m2-1)>mid&&nums[m2-1]==target)
        {
            end=m2-1;
            break;
        }
        if(nums[m2]==target&&(m2+1)<nums.size()&&nums[m2+1]==target) m1=m2+1;
        if(nums[m2]>target&&(m2-1)>mid&&nums[m2-1]>target) high=m2-1;
    }
    return {begin,end};
}


int main() {
    vector<int> a={1,2,3};

    int target=1;
    vector<int> ans=searchRange(a,target);
    std::cout << ans[0]<<ans[1]<< std::endl;
    return 0;
}