3-line binary search in sorted array { citations[i]-(n-i) } for first element >= 0


  • 0

    Note that if array { citations[i] } is already sorted, so is { citations[i]-(n-i) }.
    Therefore, find first index i in sorted array { citations[i]-(n-i) } such that citations[i]-(n-i) >= 0, then the answer is n-i.

        int hIndex(vector<int>& c) {
            int L = -1, R = c.size(), mid;// index range [0,n] = (-1,n] for int
            while(R - L > 1) if(c[mid = L + (R - L)/2] >= c.size() - mid) R = mid; else L = mid;
            return c.size() - R;
        }
    

Log in to reply
 

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