Leetcode: H-Index ||

 Difficulty: Medium

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.

---------------------------------------------------

Using binary search untill l>r:

When citations[mid]<len-mid,
                l=mid+1;
                mid=(l+r)/2;

When  citations[mid]>=len-mid,
               r=mid-1;
               mid=(l+r)/2;

As following examples show:

In the end, when l>r, the L will be in the right position.


////////////////////////////////////////////////////
//CODES

class Solution {

 public:

        int hIndex(vector<int>& citations) {

               //check input

               int len = citations.size();

               if (len == 0)return 0;

               //binary search

               int l = 0, r = len - 1, mid = (l + r) / 2;

               while (l <= r){

                      if (citations[mid]<len - mid){

                            l = mid + 1;

                            mid = (l + r) / 2;

                      }

                      else{

                            r = mid - 1;

                            mid = (l + r) / 2;

                      }

               }

               return len - l;

        }

 };