[Java/Python 3] Sort and Binary Search, w/ brief explanation and analysis.
Try to use small numbers in subsequence so that we can make it as long as possible. Therefore, it is logical to sort the input array and then use prefix sum arr
Try to use small numbers in subsequence so that we can make it as long as possible. Therefore, it is logical to sort the input array and then use prefix sum array to binary search to locate the longest size.\n\n```java\n    public int[] answerQueries(int[] nums, int[] queries) {\n        int m = queries.length, n = nums.length, i = 0;\n        Arrays.sort(nums);\n        int[] prefixSum = new int[n + 1];\n        for (int num : nums) {\n            prefixSum[i + 1] = prefixSum[i++] + num;\n        }\n        i = 0;\n        int[] ans = new int[m];\n        for (int q : queries) {\n            ans[i++] = binarySearch(prefixSum, q) - 1;\n        }\n        return ans;\n    }\n    private int binarySearch(int[] a, int k) {\n        int lo = 0, hi = a.length;\n        while (lo < hi) {\n            int mid = lo + (hi - lo) / 2;\n            if (a[mid] <= k) {\n                lo = mid + 1;\n            }else {\n                hi = mid;\n            }\n        }\n        return lo;\n    }\n```\n\n----\n\n\n**Q & A**\n\nQ1: `ans.append(bisect.bisect_right(prefix_sum, q) - 1)` - what does this line mean?\nA1: `bisect.bisect_right(prefix_sum, q)` - Binary seach to find the largest index `idx` such that all `prefix_sum[ : idx] <= q` and all `prefix_sum[idx :] > q`. Since we put a dummy value `0` in the front of the prefix sum array `prefix_sum`, it is necessary to deduct `1` from `idx`. Therefore, `idx - 1` is the longest size of subsequence that is no greater than `q`.\n\n**End of Q & A**\n\n\n```python\n    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:\n        nums.sort()\n        prefix_sum = [0]\n        for n in nums:\n            prefix_sum.append(prefix_sum[-1] + n)\n        ans = []    \n        for q in queries:\n            ans.append(bisect.bisect(prefix_sum, q) - 1)\n        return ans\n```\nOr shorter\n\n```python\n    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:\n        prefix_sum = [0]\n        for n in sorted(nums):\n            prefix_sum.append(prefix_sum[-1] + n)\n        return [bisect_right(prefix_sum, q) - 1 for q in queries]\n```\n**Analysis:**\n\nTime: `O((m + n)logn)`, space: `O(m + n)` - including sorting space, where `m = queries.length, n = nums.length`.
['Java', 'Python3']