binary search + python3
Intuition\nSimilar to the editorial solution, but with binary search implemented in details\n\n\n# Complexity\n- Time complexity:\nO(NlogN)\n\n\n\n# Code\n\ncla
# Intuition\nSimilar to the editorial solution, but with binary search implemented in details\n\n\n# Complexity\n- Time complexity:\nO(NlogN)\n\n\n\n# Code\n```\nclass Solution:\n    def numSubseq(self, nums: List[int], target: int) -> int:\n        nums = sorted(nums)\n        #binary search, find the range that has minimum and maximum <=9\n        l = 0\n        r = len(nums)-1\n        mod = 10**9+7\n\n        def binary_search(l, r, nums, target):\n            #Need to find where target - nums[0] is in the array. \n            #Need to find the right boundary\n\n            #Using the ultimate template\n            while l<=r:\n                mid = l + (r-l)//2\n                if nums[mid] < target:\n                    l = mid + 1\n                elif nums[mid] > target:\n                    r = mid - 1\n                elif nums[mid] == target:\n                    l = mid + 1\n            #Do not need to do edge case check. Because it will be done in the for loop below\n            return l-1\n        \n        res = 0\n        for l in range(len(nums)):\n            if nums[l]>target:\n                break #if the smallest number being checked is already larger than target, there is no chance for getting a meaningful r2 to build subsequences that satisfy the requirement\n            r2 = binary_search(l, r, nums, target-nums[l])\n            if r2>=l:\n                res += pow(2, r2-l, mod)# Note, if we find [2, \'3\', 4, 5, 6, 7, \'8\'] (\'x\' means left and r2, respectively), for the l==3, any subsequence including 4 to 8 (5 numbers) satisfy the requirement. Thus, it is r2-l, because there are this many numbers (5 numbers in this example)\n        return res % mod\n```
['Binary Search', 'Python3']