https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

我的方法一：分治递归【超时】

步骤：

1. 每次找到中间点
2. 判断中间点middle是否是target，如果middle==target，则递归左边和右边，如果middle<target，则只递归右边；如果middle>target，则只递归左边；然后将获得结果的区间返回；

初始条件

边界条件

1. nums长度为0，直接返回[-1, -1]

复杂度

时间复杂度：分治法，O(logn)
空间复杂度：递归，O(logn)

超时代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        return searchRange(nums, 0, nums.size() - 1, target);
    }

    //include begin and end
    vector<int> searchRange(vector<int>& nums, int begin, int end, int target) {
        if(begin > end){
            return {-1, -1};
        }else if(begin == end){
            if(nums[begin] == target){
                return {begin, begin};
            }else{
                return {-1, -1};
            }
        }

        int middle = (begin + end)/2;
        if(nums[middle] == target){
            int min = -1;
            int max = -1;

            vector<int> ret_left = searchRange(nums, 0, middle - 1, target);
            vector<int> ret_right = searchRange(nums, middle+1, end, target);
            if(ret_left[0] != -1){
                min = ret_left[0];
            }else if(ret_left[1] != -1){
                min = ret_left[1];
            }else{
                min = middle;
            }

            if(ret_right[1] != -1){
                max = ret_right[1];
            }else if(ret_right[0] != -1){
                max = ret_right[0];
            }else{
                max = middle;
            }
            return {min, max};
        }else if(nums[middle] > target){
            return searchRange(nums, 0, middle - 1, target);
        }else{
            return searchRange(nums, middle+1, end, target);
        }
    }
};

我的方法二：分治迭代

既然递归超时了，可能是函数栈耗时造成的，所以用迭代试试

步骤：

1. 先求min的位置，再求max的位置
2. 先求min，从middle位置开始找，如果middle=target，那么min应该在(0, middle)之间；如果middle<target，那么min应该在(middle+1, end)，如果middle>target，那么min应该在(begin, middle-1)，直到区间的开始和结束相等时；
3. 相同道理，再求max，从middle位置开始找，如果middle=target，那么max应该在(middle, end)之间；如果middle<target，那么max应该在(middle+1, end)，如果middle>target，那么max应该在(begin, middle-1)，直到区间的开始和结束相等时；

初始条件

1. begin = 0
2. end = nums.size()-1
3. min = -1, max = -1

边界条件

1. nums长度为0，直接返回[-1, -1]
2. 如果求的min=-1，那么max=-1
3. 如果min!=0，那么max应该在(min, end)之间找
4. 

复杂度

时间复杂度：分治法，O(logn)
空间复杂度：递归，O(1)

代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size()==0){
            return {-1, -1};
        }

        int begin = 0;
        int end = nums.size()-1;
        int min = -1;
        int max = -1;
        int middle = 0;
        
        //find min
        while(begin <= end){
            middle = (begin+end)>>1;
            if(nums[middle] == target){
                if(end == middle){
                    end = middle - 1;
                }else{
                    end = middle;
                }
                min = middle;
            }else if(nums[middle] < target){
                begin = middle + 1;
            }else{
                end = middle - 1;
            }

            //cout<<"min begin:"<<begin<<" end:"<<end<<" mid:"<<middle<<endl;
        }

        if(min == -1){
            return {-1, -1};
        }

        //find max
        begin = min;
        end = nums.size() -1;
        while(begin <= end){
            middle = (begin+end)>>1;
            //cout<<"max begin:"<<begin<<" end:"<<end<<" mid:"<<middle<<endl;
            if(nums[middle] == target){
                if(begin < middle){
                    begin = middle;
                } else {
                    begin = middle+1;
                }
                max = middle;
            }else if(nums[middle] < target){
                begin = middle + 1;
            }else{
                end = middle - 1;
            }
        }

        return {min, max};
    }
};