Java Binary Search Solution with Explanation
\nclass Solution {\n    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {\n        // 1. define search space\n        long left = (long)-1e11;\
```\nclass Solution {\n    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {\n        // 1. define search space\n        long left = (long)-1e11;\n        long right = (long)1e11;\n        while(left < right){\n            long mid = left + (right - left) / 2;\n            if(countSmaller(nums1, nums2, mid) >= k){\n                right = mid;\n            } else {\n                left = mid + 1;\n            }\n        }\n        // At the end, left is the product that has k smaller products before it, so the kth smallest product is left - 1\n        return left - 1;\n    }\n    \n    private long countSmaller(int[] nums1, int[] nums2, long product){\n        long count = 0;\n        for(int i = 0; i < nums1.length; i++){\n            // count all nums2[j] such that nums1[i] * nums2[j] < product\n            if(nums1[i] >= 0){\n                int left = 0;\n                int right = nums2.length;\n                while(left < right){\n                    int mid = left + (right - left) / 2;\n                    // if nums1[i] > 0, find the first occurrence of nums2[j] where nums1[i] * nums2[j] >= product\n                    if((long) nums1[i] * nums2[mid] < product){\n                        left = mid + 1;\n                    } else {\n                        right = mid;\n                    }   \n                }\n                count += left;\n            } else {\n                int left = 0;\n                int right = nums2.length;\n                while(left < right){\n                    int mid = left + (right - left) / 2;\n                    // since nums1[i] is negative, nums2 is sorted\n                    // nums[j] * nums[i] will be in descending order from [0...nums2.length-1]\n                    // take [-4,-2,0,3] as an example, product with a negative number will become smaller if the number gets bigger\n                    // want to find the last nums2[j] such that nums1[i] * nums2[j] is not smaller than product\n                    if((long) nums1[i] * nums2[mid] >= product){\n                        left = mid + 1;\n                    } else {\n                        right = mid;\n                    }\n                }\n                count += nums2.length - left;\n            }\n        }\n        return count;\n    }\n}\n```
['Binary Tree', 'Java']