[LeetCode]H-Index II

H-Index II

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

二分查找，时间复杂度O(logn)。

 1 class Solution {
 2 public:
 3     int hIndex(vector<int>& citations) {
 4         int n = citations.size();
 5         if(n==0) return 0;
 6         int left=0,right=citations.size()-1;
 7         while(left<=right)
 8         {
 9             int mid = (left+right)/2;
10             if(citations[mid]==(n-mid))
11             {
12                 return (n-mid);
13             }
14             else if(citations[mid]<(n-mid))
15             {
16                 left = mid+1;
17             }
18             else
19             {
20                 right = mid-1;
21             }
22         }
23         return (n-left);
24     }
25 };