[数据结构与算法]【leetcode】二分法-34.在排序数组中查找元素的第一个和最后一个位置

题目：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。

题目分析：不考虑时间复杂度的话，可以直接遍历该列表，记录target所在的所有位置存放在一个vector中，如果遍历结束，该vector为空，则说明给定数组中没有target值；若该vector的size==1，则说明target只出现过一次，那么在补充填入一个结束位置即可；否则，该target在数组中出现多次，那么vector的长度可能大于2，仅需要提取第一个元素和末尾元素，即是target出现的开始位置和结束位置。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int>range;
        vector<int>ans;
        for(int i = 0;i<nums.size();i++)
        {
            if(nums[i] ==target )
            {
                range.push_back(i);
            }
        }
        if(range.size()==0)
        {
            ans.push_back(-1);
            ans.push_back(-1);
        }
        else if(range.size()==1)
        {
            ans.push_back(range[0]);
            ans.push_back(range[0]);
        }
        else
        {
            ans.push_back(range[0]);
            ans.push_back(range[range.size()-1]);
        }
        return ans;
    }
};

执行用时：8 ms, 在所有 C++ 提交中击败了68.07%的用户
内存消耗：13.4 MB, 在所有 C++ 提交中击败了18.60%的用户

进阶：
可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

分析：O(log n)为二分法的复杂度，通过二分法，确定target的开始和结束位置。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int>range;
        if(nums.size()!=0)
        {
            int a = 0,b = nums.size()-1;//用来记录开始的区间
            int c = 0,d = INT_MAX;//用来记录结束的区间
            bool no = false,no2= false;//标识是否遍历到过target
            int times=0;//表示第几次遍历到target，只有第一次才需要设置cd
            while(a<b || (c<d && d!=INT_MAX ))
            {
                //no = false;
                //no2 = false;
                if(a<b)
                {
                    int middle = (a+b)/2;
                    if(nums[middle]!=target)
                    {
                        if(nums[middle]<target)
                        {
                            a = middle+1;
                            b = b;
                        }
                        else
                        {
                            a = a;
                            b = middle-1;
                        }
                    }
                    else
                    {
                        if(times==0)
                        {
                            no = true;
                            a = a;
                            d = b;
                            c = middle+1;
                            b = middle-1;
                            times++;
                        }
                        else
                        {
                            a = a;
                            b = middle-1;
                        }
                    }
                }
                if(d!=INT_MAX && c<d )
                {
                    int middle2 = (c+d)/2;
                    if (nums[middle2]!=target)
                    {
                        if (nums[middle2]>target)
                        {
                            c = c;
                            d = middle2-1;
                        }
                        else
                        {
                            c = middle2+1;
                            d = d;
                        }
                    }
                    else
                    {
                        c = middle2+1;
                        d = d;
                        //no2 = true;
                    }
                }
            }
            if(nums[a]==target && nums[c]==target)
            {
                range.push_back(a);
                range.push_back(c);
            }
            else if(nums[a]==target && nums[c]!=target)
            {
                range.push_back(a);
                if(no==false)
                {
                    range.push_back(a);
                }
                else
                {
                    range.push_back(c-1);
                }
            }
            else if(nums[a]!=target && nums[c]==target)
            {
                if(no==false)
                {
                    range.push_back(c);
                }
                else
                {
                    range.push_back(a+1);
                }
                range.push_back(c);
            }
            else
            {
                if(no==false)
                {
                    range.push_back(-1);
                    range.push_back(-1);
                }
                else
                {
                    range.push_back(a+1);
                    range.push_back(c-1); 
                }
            }
        }
        else
        {
            range.push_back(-1);
            range.push_back(-1);
        }
        return range;
    }
};

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：13.4 MB, 在所有 C++ 提交中击败了7.65%的用户