[C++] Binary Search O(NlogNlogA), (1728 ms, 24.71% / 89.7 MB, 74.15% )
My main idea is to rewrite the problem description as follows,\n"Find the minimum integer which is larger than at least k products made with nums1 and nums2.".\
My main idea is to rewrite the problem description as follows,\n"Find the minimum integer which is larger than at least k products made with nums1 and nums2.".\nThis problem can be solved by a binary search technique.\n\nThe complexity is O(NlogNlogA), where N denotes max(nums1.size(), nums2.size()) and A denotes the size of the range. Here,\nthe range is set [-1e10, 1e10] so A is 2e10.\n\n\n```c++\ntypedef long long int ll;\n\nclass Solution {\npublic:\n    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {\n        ll left = -(ll)(1e10) - 1;\n        ll right = (ll)(1e10) + 1;;\n        while(right - left > 1){\n            ll c = (left + right)/2;\n            ll num = 0;\n            for(int n : nums1){\n                if(n == 0){\n                    if(c >= 0){\n                        num += nums2.size();\n                    }\n                }else if(n > 0){\n                    ll f = floor(c/(double)n);\n                    auto iter = upper_bound(nums2.begin(), nums2.end(), f);\n                    num += iter - nums2.begin();\n                }else{\n                    ll f = ceil(c / (double)n);\n                    auto iter = lower_bound(nums2.begin(), nums2.end(), f);\n                    num += nums2.size() - (iter - nums2.begin());             \n                }\n            }\n            if(num >= k){\n                right = c;\n            }else{\n                left = c;\n            }\n        }\n        return right;\n    }\n}\n```
['Binary Tree']