Binary Search Only C++
Intuition\n Describe your first thoughts on how to solve this problem. \n\n1) We could do it using min Heap like this https://leetcode.com/problems/find-k-pairs
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n1) We could do it using min Heap like this [https://leetcode.com/problems/find-k-pairs-with-smallest-sums/description/]()  but the constraint for k is of the order 10^9 something. So we can not use min heap here.\n\n2) If I consider midVal to be the Kth smallest then the number of products less than midVal must be K - 1;\n3) If the number of products less than midVal is **x** then number of products less than midVal + 1 will be greater than or equal to **x**.\nThe same thing goes for midVal + 2 and so on.\n\n4) It means we can apply binary search on this midVal. And try to find smallest midVal which is having k - 1 number of products less than midVal.\n\n\n5) In order to count the product which is less than midVal.We can fix one value one and try to find the other value using binary search.\n\n\n# Code\n```\nclass Solution {\npublic:\n\n    bool helper(vector<int>& nums1, vector<int>& nums2, long long k, long long midVal) {\n\n        int n = nums1.size();\n        int m = nums2.size();\n\n        long long cnt = 0;\n\n        for(int i = 0; i < n; i++) {\n\n            long long val = nums1[i];\n\n            if(val == 0 && midVal >= 0) {\n                cnt += m;\n            } else if(val > 0) {\n                int maxIdx = -1;\n                int l = 0;\n                int r = m - 1;\n                while(l <= r) {\n                    int mid = l + (r - l) / 2;\n                    long long product = nums2[mid] * val * 1LL;\n                    if(product <= midVal) {\n                        maxIdx = mid;\n                        l = mid + 1;\n                    } else {\n                        r = mid - 1;\n                    }\n                }\n                if(maxIdx != -1) {\n                    cnt += (maxIdx + 1);\n                }\n            } else if(val < 0){\n                int minIdx = -1;\n                int l = 0;\n                int r = m - 1;\n                while(l <= r) {\n                    int mid = l + (r - l) / 2;\n                    long long product = nums2[mid] * val * 1LL;\n                    if(product <= midVal) {\n                        minIdx = mid;\n                        r = mid - 1;\n                    } else {\n                        l = mid + 1;\n                    }\n                }\n                if(minIdx != -1) {\n                    cnt += (m - minIdx);\n                }\n            }\n        }\n\n\n        if(cnt >= k) {\n            return true;\n        } else {\n            return false;\n        }\n\n    }\n \n\n\n\n    \n    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {\n        \n\n        long long left = -1e13;\n        long long right = 1e13;\n\n        long long ans;\n\n        while(left <= right) {\n            long long midVal = left + (right - left) / 2;\n\n            bool poss = helper(nums1, nums2, k, midVal);\n\n            if(poss) {\n                ans = midVal;\n                right = midVal - 1;\n            } else {\n                left = midVal + 1;\n            }\n\n        }\n\n\n        return ans;\n\n    }\n};\n```
['Binary Search', 'C++']