C++ 12ms using binary search


  • 0
    Z
    class Solution {
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
            int size = nums.size();
            int start = 0, end = size-1;
            bool bFound = false;
            vector<int> res;
            int half;
            
           
            
            while(start <= end && start < size && end>=0)
            {
                half = (start + end)/2;
                
                if (nums[half] == target)
                {
                    bFound = true;
                    break;
                }
                else if (nums[half] < target)
                {
                    start = half +1;
                }
                else
                {
                    end = half - 1;
                }
            }
            
            if(bFound)
            {
                //check left
                int left = 0, right = size -1;
                int pos1 = half, pos2 = half;
                while(pos1 >0 && nums[pos1-1] == target)
                {
                    pos1--;
                    int mid = (left + pos1)/2;
                    if (nums[mid] < target)  left = mid;
                    else pos1 = mid;
                }
                
                //check right
                while(pos2 < (size-1) && nums[pos2+1] == target)
                {
                    pos2++;
                    int mid = (right + pos2)/2;
                    if (nums[mid] > target) right = mid;
                    else pos2 = mid;
                }
                res.push_back(pos1);
                res.push_back(pos2);
            }
            else
            {
                res.push_back(-1);
                res.push_back(-1);
            }
            return res;
        }
    };

  • 0
    C

    I think you can change if (nums[mid] < target) left = mid to if (nums[mid] < target) left = mid + 1, and
    if (nums[mid] > target) right = mid to if (nums[mid] > target) right = mid - 1


Log in to reply
 

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