[Python] binary search solution, explained
The idea of this problem is to use binary search: let check(x) be the answer to the question: how many products are less or equal than x. Then we use binary sea
The idea of this problem is to use binary search: let `check(x)` be the answer to the question: how many products are less or equal than `x`. Then we use binary search and find the first moment where we have exactly `k` such numbers.\n\n1. If `n1` is positive, then values in `nums2 * n1` go in increasing order, so we use bisect to find number of values which are `<= x//n1`.\n2. If `n1` is negative, then values in `nums2 * n1` going in decreasing order, so we need to take the right part.\n3. If `n1` equal to `0`, than all values in `nums2 * n1` are equal to `0`. So, we update `total` only if `x >= 0`.\n\n#### Complexity\nTime complexity is `O(n*log m* log N)`, where `n = len(nums1)`, `m = len(nums2)` and `N = 10**10 + 10` is the maximum value of product. Space complexity is `O(1)`\n\n\n#### Code\n```python\nfrom bisect import bisect, bisect_left\n\nclass Solution:\n    def kthSmallestProduct(self, nums1, nums2, k):\n        def check(x):\n            total = 0\n            for n1 in nums1:\n                if n1 > 0: total += bisect(nums2, x//n1)\n                if n1 < 0: total += len(nums2) - bisect_left(nums2, ceil(x/n1))\n                if n1 == 0 and x >= 0: total += len(nums2)\n\n            return total\n\n        beg, end = -10**10 - 1, 10**10 + 1\n\n        while beg + 1 < end:\n            mid = (beg + end)//2\n            if check(mid) >= k:\n                end = mid\n            else:\n                beg = mid\n\n        return beg + 1\n```\n\nIf you have any questoins, feel free to ask. If you like the solution and explanation, please **upvote!**
['Binary Search']