###### tags: `LeetCode` `Medium`
# LeetCode #275 [H-Index II](https://leetcode.com/problems/h-index-ii)
### (Medium)
給你一個整數數組 citations ，其中 citations[i] 表示研究者的第 i 篇論文被引用的次數，citations 已經按照 升序排列 。計算並返回該研究者的 h 指數。
h 指數的定義：h 代表“高引用次數”（high citations），一名科研人員的 h 指數是指他（她）的 （n 篇論文中）總共有 h 篇論文分別被引用了至少 h 次。且其餘的 n — h 篇論文每篇被引用次數 不超過 h 次。
提示：如果 h 有多種可能的值，h 指數 是其中最大的那個。
請你設計並實現對數時間複雜度的算法解決此問題。

---
O(n)解法 :
由於已經按照大小排序, 則可遍歷citations[i], 若citations[i]的值大於等於n-i的值, 則答案為n-i。
EX: citations = {0,1,2,3,4,5,6,7,8,9,10,11}, 則大於等於7的論文篇數為5, 大於等於6的為6, 大於等於5的為7。
if(citations[i]≥n-i) return n-i;
判斷式citations[i]≥n-i代表的確有足夠篇數滿足而數量為n-i, 於是回傳滿足的篇數(最大值為citations[i])。

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n=citations.size();
        if(n){
            for(int i=0;i<n;i++){
                if(citations[i]>=n-i)return n-i;
            }
            return 0;
        }
        return 0;
    }
};

---
O(logn)解法 - 二元搜尋
與上面相似, 目的皆為找到citations[i]≥n-i, 只是搜尋方式不同。

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n=citations.size();
        if(n){
            int low=0, high=n-1, ans=0;
            while(low<=high){
                int mid = low + (high-low)/2;
                if(citations[mid]>=n-mid){
                    ans=n-mid;
                    high=mid-1;
                }
                else{
                    low=mid+1;
                }
            }
            return ans;
        }
        return 0;
    }
};