C++ Binary Search (O(n logn))


  • 0
    R
    int BS(int l,int r,int* arr,int num)
    {
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(arr[mid]>=num)r=mid;
            else l=mid+1;
        }
        return l;
    }
    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int q[50005],tail=1;
            for(int i=0;i<nums.size();i++)
            {
                int p=BS(1,tail,q,nums[i]);
                q[p]=nums[i];
                if(tail<=p)tail=p+1;
            }
            return tail-1;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.