給定一位研究者論文被引用次數(shù)的數(shù)組（被引用次數(shù)是非負整數(shù)），數(shù)組已經按照升序排列。編寫一個方法榜苫，計算出研究者的 h 指數(shù)。

h 指數(shù)的定義: “h 代表“高引用次數(shù)”（high citations）翎冲，一名科研人員的 h 指數(shù)是指他（她）的 （N 篇論文中）總共有 h 篇論文分別被引用了至少 h 次垂睬。（其余的 N - h 篇論文每篇被引用次數(shù)不多于 h 次。）"

示例:

輸入: citations = [0,1,3,5,6]
輸出: 3
解釋: 給定數(shù)組表示研究者總共有 5 篇論文抗悍，每篇論文相應的被引用了 0, 1, 3, 5, 6 次驹饺。
由于研究者有 3 篇論文每篇至少被引用了 3 次，其余兩篇論文每篇被引用不多于 3 次缴渊，所以她的 h 指數(shù)是 3赏壹。

說明:

如果 h 有多有種可能的值 ，h 指數(shù)是其中最大的那個衔沼。

進階：

這是 H指數(shù) 的延伸題目蝌借，本題中的 citations 數(shù)組是保證有序的昔瞧。
你可以優(yōu)化你的算法到對數(shù)時間復雜度嗎？

本題看到要對數(shù)復雜度菩佑，并且是有序的自晰，那就想到了二分算法。
算法很輕松的就想到了稍坯，但是處理本題沒那么簡單酬荞，因為本題的判斷和返回值和普通的二分查找是不一樣的。
我們設數(shù)組總數(shù)為n
當 citations[mid] == n - mid 相同的時候瞧哟，我們直接返回n - mid混巧。
否則我們就要進行判斷

• 如果 citations[mid] > n - mid 就說明，該數(shù)不可能是H指數(shù)绢涡，那就說明H指數(shù)存在的話就一定在前面牲剃。
• 如果citations[mid] < n-mid 就說明，該數(shù)是H指數(shù)雄可，但是不一定是最大H指數(shù)凿傅，我們往后查詢看看。

本題我們需要返回的是n - mid 因為H指數(shù)不是一定在數(shù)組中一定存在的数苫，而是一個根據(jù)定義生成的數(shù)字聪舒。
最后如果找不到那個citations[mid] == n - mid的數(shù)，那就說明H指數(shù)并不在數(shù)組中存在虐急，因為我們始終會去找到H指數(shù)箱残，然后在找到的基礎上進行繼續(xù)縮小范圍，最后low指向的是可以形成H指數(shù)的數(shù)止吁，或是第一個數(shù)被辑，high與low相等，這時候low會加一從而退出循環(huán)敬惦，因此我們最后要返回n-low盼理。
代碼如下:

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

    }
}

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/h-index-ii
著作權歸領扣網絡所有。商業(yè)轉載請聯(lián)系官方授權俄删，非商業(yè)轉載請注明出處宏怔。