[Python] Binary Search, O((m+n)log10^10)
Intuition\nBinary search the result, and count the number of smaller product.\n\nWe can firstly consider the simple situation with no negatives.\nThe base of th
# **Intuition**\nBinary search the result, and count the number of smaller product.\n\nWe can firstly consider the simple situation with no negatives.\nThe base of this question is the two sum problem.\n\nIn two sum problem,\nwe can count the number of pair with sum <= x.\n\nIn this two product problem,\nwe need to count the number of pair with product <= x.\n<br>\n\n# **Complexity**\nTime `O((m+n)log10^10)`\nSpace `O(n+m)`\n<br>\n\n**Python**\n```py\n    def kthSmallestProduct(self, A, B, k):\n        n, m = len(A), len(B)\n        A1,A2 = [-a for a in A if a < 0][::-1], [a for a in A if a >= 0]\n        B1,B2 = [-a for a in B if a < 0][::-1], [a for a in B if a >= 0]\n\n        neg = len(A1) * len(B2) + len(A2) * len(B1)\n        if k > neg:\n            k -= neg\n            s = 1\n        else:\n            k = neg - k + 1\n            B1, B2 = B2,B1\n            s = -1\n\n        def count(A, B, x):\n            res = 0\n            j = len(B) - 1\n            for i in xrange(len(A)):\n                while j >= 0 and A[i] * B[j] > x:\n                    j -= 1\n                res += j + 1\n            return res\n\n        left, right = 0, 10**10\n        while left < right:\n            mid = (left + right) / 2\n            if count(A1, B1, mid) + count(A2, B2, mid) >= k:\n                right = mid\n            else:\n                left = mid + 1\n        return left * s\n```\n
[]