Two different binary search solutions in C, accepted as best


  • 1
    //AC - 4ms;
    int hIndex1(int* nums, int size)
    {
        int l=0, r=size-1;
        while(l <= r)
        {
            int m = l+(r-l)/2;
            if(size-m < nums[m]) r = m-1;
            else if(size-m > nums[m]) l = m+1;
            else r--; //ensure the loop will terminate properly;
        }
        return size-l;
    }
    

    Actually we can just return if size-m == nums[m] since the array is ordered the left side will always be equal to or smaller than nums[m].

    //AC - 4ms;
    int hIndex(int* nums, int size)
    {
        int l=0, r=size-1;
        while(l <= r)
        {
            int m = l+(r-l)/2;
            if(size-m == nums[m]) return nums[m]; //exactly fit in, just return;
            if(size-m < nums[m]) r = m-1;
            else l = m+1;
        }
        return size-l;
    }

Log in to reply
 

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