Sandbox::https://github.com/tscui/leetcode-1/blob/master/algorithms/cpp/h-Index/h-Index.II.cpp

Repository navigation

33 lines (28 loc) · 935 Bytes

// Source : https://leetcode.com/problems/h-index-ii/

// Author : Hao Chen

// Date : 2015-11-08

/***************************************************************************************

* Follow up for H-Index: What if the citations array is sorted in ascending order?

* Could you optimize your algorithm?

***************************************************************************************/

class Solution {

public:

// binary search - O(log(n))

int hIndex(vector<int>& citations) {

int n = citations.size();

int low = 0, high = n-1;

while( low <= high ) {

int mid = low + (high-low)/2;

if (citations[mid] == n - mid) {

return n - mid;

}else if (citations[mid] > n-mid){

high = mid - 1;

}else {

low = mid + 1;

}

return n-low;

}

};