275. H-Index II

275. H-Index II (#1 Search in value).java

//Find the h in the range of [0, citations.length], not in the array
//Runtime: O(logn) 14ms
class Solution {//[0,3,3]  [3,3,3] [] [0] [0,0] [2] [0,0,4,4] [0,1,1,2]
    public int hIndex(int[] citations) {
        int begin = 0, end = citations.length, mid, h = 0;
        if(citations.length > 0) {
            h = Math.min(citations.length, citations[0]);
        }
        
        while(begin <= end) {
            mid = begin + (end - begin) / 2;  //Possible h value
            int i = citations.length - mid;  //There are mid elements which are larger than citations[i]
            if(i == citations.length) {
                break;
            }
            
            //To check if mid is possible, check citations[i] to see if there are mid elements which are larger than mid.
            if(mid == citations[i]) {
                return mid;
            } else if(mid < citations[i]) {
                h = mid;
                begin = mid + 1;
            } else if(mid > citations[i]) {
                h = Math.max(h, citations[i]);  //[0,1,1,2] [0,0,4,4]
                end = mid - 1;
            }
        }
        return h;
    }
}

275. H-Index II (#2 Search in array).java

//Find the h in the array.
//If there is no such element, we can get h from the base-1 index.
class Solution {
    public int hIndex(int[] citations) {
        int len = citations.length;
        if(len == 0) return 0;
        int begin = 0, end = len - 1, mid;
        
        //To find an i that satisfies citations[i] >= base-1 index[i]
        while(begin <= end) {
            mid = begin + (end - begin) / 2;
            int index = len - mid;  //The number of elements after citations[mid] (inclusive) is target
            
            if(citations[mid] == index) {
                return index;
            } else if(citations[mid] < index) {
                begin = mid + 1;
            } else {//citations[mid] > index
                end = mid - 1;
            }
        }
        
        //begin == end - 1, now the right one(citations[begin]) is the most left element that satisfies citations[i] >= base-1 index[i]
        return len - begin;
    }
}