Java Double Binary Search O(log10^10 x MlogN)
Thinking Process\n I can put the index pair for the two arrays in a priority queue and compute the answer gradually. However, the K can be up to 10^9. This will
**Thinking Process**\n* I can put the index pair for the two arrays in a priority queue and compute the answer gradually. However, the K can be up to 10^9. This will lead to TLE.\n* The element can be negative. Maybe I need to know the number of negative elements and handle 4 different combinations: (negative array 1, negative array 2), (negative array 1, positive array 2), (positive array 1, negative array 2), (positive array 1, positive array 2). At least, I can know the number of products of each combination and locate k-th product among them.\n* Even though I know which combination the k-th product belongs to, it doesn\'t guarantee I can use the priority queue approach. I need another hint.\n* Continue with above, I think I need some way to eliminate some number of products step by step to reach the goal.\n* Since the array is sorted, if I turn my attention on nums1[i] x nums2[j], I can know there are j + 1 products which are less than or equal to nums1[i] x nums2[j] that are generated by nums1[i]. Then I realize that I should try the binary search.\n\n**Algorithm**\n* Binary search the answer\n* For each nums1[i], count the number of products that are less than or equal to the current guess\n\n**Quick Implementation during the contest** \n```\nclass Solution {\n    static long INF = (long) 1e10;\n    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {\n        int m = nums1.length, n = nums2.length;\n        long lo = -INF - 1, hi = INF + 1;\n        while (lo < hi) {            \n            long mid = lo + ((hi - lo) >> 1), cnt = 0;\n            for (int i : nums1) {\n                if (0 <= i) {\n                    int l = 0, r = n - 1, p = 0;\n                    while (l <= r) {\n                        int c = l + ((r - l) >> 1);\n                        long mul = i * (long) nums2[c];\n                        if (mul <= mid) {\n                            p = c + 1;\n                            l = c + 1;\n                        } else r = c - 1;\n                    }\n                    cnt += p;\n                } else {\n                    int l = 0, r = n - 1, p = 0;\n                    while (l <= r) {\n                        int c = l + ((r - l) >> 1);\n                        long mul = i * (long) nums2[c];\n                        if (mul <= mid) {\n                            p = n - c;\n                            r = c - 1;\n                        } else l = c + 1;\n                    }\n                    cnt += p;\n                }\n            }\n            if (cnt >= k) {\n                hi = mid;\n            } else lo = mid + 1L;\n        }\n        return lo;\n    }\n}\n```
['Binary Tree', 'Java']