H-Index II -- Leetcode

Question:

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

Hint:

1. Expected runtime complexity is in O(log n) and the input is sorted.

Answer:

Keyword: Binary Search, O(log n).

    //0,3,7,8,9

    public int hIndex(int[] citations) {

        int len = citations.length;

        int start = 0;

        int end = len - 1;

        while(start <= end){

            int mid = start + (end - start) / 2;

            

            int index = len - mid;

            if(citations[mid] >= index && (mid == 0 || citations[mid-1] <= index) ){

                return index;

            }else if(citations[mid] < index){

                start = mid + 1;

            }else{

                end = mid - 1;

            }

        }

        return 0;

    }