H-Index II (Binary Search)

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

 

public class Solution {
    public int hIndex(int[] citations) {
        //binary search
        int len = citations.length; 
        int low = 0; 
        int high = len - 1; 
        int mid = 0; 
        while (low <= high) {
            mid = low + (high - low)/2; 
            if (citations[mid] == len - mid) return len - mid; 
            else if (citations[mid] > len - mid) high = mid - 1; 
            else if (citations[mid] < len - mid) low = mid + 1; 
        }
        return len - low; 
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s