Share my C++ solution,easy to understand


  • 0
    V
    class Solution {
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
            vector<int> ret(2, -1);
            int n = nums.size();
            int left = 0, right = n-1, mid = 0;
    
            if (n == 0 || nums[0] > target || nums[n-1] < target)
                return ret;
            if (nums[0] == nums[n-1])
            {
                ret[0] = 0;
                ret[1] = n-1;
                
                return ret;
            }
            
            //find the starting position
            while (left <= right)
            {
                mid = left + (right - left) / 2;
                if (nums[mid] == target)
                {
                    right = mid;
                    if (left == right)
                        break;
                }
                else if (nums[mid] > target)
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            if (left > right)
                return ret;
                
            ret[0] = left;
            if ((left + 1 < n && nums[left] != nums[left+1]) || left == n-1)
            {
                ret[1] = left;
                return ret;
            }
            
            //find the ending position
            right = n-1;
            while (left <= right)
            {
                mid = left + (right - left) / 2;
                if (nums[mid] > target)
                    right = mid - 1;
                else
                    left = mid + 1;
            }
    
            ret[1] = right;
            
            return ret;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.