My 12ms c++ concise solution


  • 0
    vector<int> searchRange(vector<int>& nums, int target) {
            int len = nums.size(), i=0, j=len-1, mid;
            vector<int> res(2,-1);
            while(i<=j)
            {
                mid = i + (j-i)/2;
                if(target == nums[mid])
                {
                    i=mid;
                    while(i>0 && nums[i]==nums[i-1]) i--;
                    while(mid<j && nums[mid]==nums[mid+1]) mid++;
                    res[0]=i;
                    res[1]=mid;
                    return res;
                }
                else if(target>nums[mid])
                {
                    i = mid+1;
                }
                else
                {
                    j = mid-1;
                }
            }
            return res;
        }
    

  • 1
    K

    Your solution seems like be in the order of O(n) although it has been accepted by leetcode.
    Just consider the worst condition that the give array is like [1,1,2,2,2,2,2,2,2,2,2,2,2] and the target is 1.
    Maybe I am wrong...


  • 0

    @KevinChan Yes, you are right. It is O(n). Thank you! Your question makes me think the two while loops are redundant. I updated the code (still O(n)). But, it doesn't change the running time. The test cases maybe not enough.


Log in to reply
 

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