Share my O(lg(n)) C++ code


  • -1
    M
    class Solution {
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
            int n=nums.size();
            vector<int>fail={-1,-1};
            if(n==0)return fail;
            if(n==1){
                if(nums[0]==target){
                    vector<int>res={0,0};
                    return res;
                }
                else return fail;
            }
            int left=0;
            int right=n-1;
            while(left<=right){
                int mid=(left+right)/2;
                if(nums[mid]==target){
                    int l,r;
                    l=r=mid;
                    while(nums[l]==target&&l>=left){
                        l--;
                    }
                    while(nums[r]==target&&r<=right){
                        r++;
                    }
                    vector<int>res={l+1,r-1};
                    return res;
                }
                else if(nums[mid]>target){
                    right=mid-1;
                }
                else{
                    left=mid+1;
                }
            }
            return fail;
        }
    };

Log in to reply
 

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