My C++ solution using binary search, 8ms and beats 98.09%


  • 0
    C
    class Solution {
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
            vector<int> ret({-1,-1});
            if(!nums.size()) return ret;
            int i = BinSearch(nums, 0, nums.size(), target);
            if(i < 0) return ret;
            else
            {
                int j = i, k = i;
                while(nums[--j] == target && j >= 0);
                while(nums[++k] == target && k < nums.size());
                ret[0] = j + 1;
                ret[1] = k - 1;
            }
            return ret;
        }
    private:
        inline int BinSearch(vector<int>& nums, int lo, int hi, int target)
        {
            while(lo < hi)
            {
                int mi = (lo + hi) >> 1;
                if(nums[mi] < target) lo = mi + 1;
                else if(nums[mi] == target) return mi;
                else if(nums[mi] > target) hi = mi;
            }
            return -1;
        }
    };
    

  • 0
    S

    The time complexity is O(n) not O(logn). The worst case is when all numbers are almost same in the array.


  • 0
    C

    @hamster You are right.But it just cost 8ms to run this algorithm while others cost more. I don't konw why. Maybe leetcode updated their server?


  • 0
    A

    @Cczhang Because leetcode testcases are all too short. Think about a vector of size 1000, with 9998 targets in it, then your O(n) would be much slower than thrice binary search.


Log in to reply
 

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