Java binary search, simple and clean


  • 18
    J

    The idea is to search for the first index from the sorted array so that :

    citations[index] >= length(citations) - index.

    And return (length - index) as the result.
    Here is the code:

    public int hIndex(int[] citations) {
    	int len = citations.length;
    	int lo = 0, hi = len - 1;
    	while (lo <= hi) {
    		int med = (hi + lo) / 2;
    		if (citations[med] == len - med) {
    			return len - med;
    		} else if (citations[med] < len - med) {
    			lo = med + 1;
    		} else { 
    			//(citations[med] > len-med), med qualified as a hIndex,
    		    // but we have to continue to search for a higher one.
    			hi = med - 1;
    		}
    	}
    	return len - lo;
    }

  • 0
    H

    Good solution! I use "while (lo < hi)" , failed for the case [0,0]

    Your solution works for this special cases [0,0] => 0 . I hope to know why you use <= rather than < .

    Thanks.


Log in to reply
 

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