Binary Search - Simple C++ Solution with explanation
Intuition\n\nWe will start with the binary search finding how many numbers are less than the current value. And will go to the left or right side based on the n
# Intuition\n\nWe will start with the binary search finding how many numbers are less than the current value. And will go to the left or right side based on the no. of elements smaller than our current value.\n\nChecking for numbers smaller than a value. Now we will iterate over the first array. \n\nNow if the current element is negative, then we will find the largest number in nums2 which is lesser than or equal to the number x/nums1[i]( removing the part added by first array). Now since the current element was negative we will take all the elements on the right side because we need all the elements that are greater.\n\nNow if the element of nums1 is postive than we will simply find the smallest number that is greater than the x/nums1[i]. Now after counting for each index if at any point the count is greater than or equal to k , we will return true else false;\n\nNow if the function returns true it means that this could be the possible answer and we will shift the binary search to the left as we want kth smallest element and currently we are getting more than k smaller elements on the left.\n\n\n\n# Approach\n\nStart with the binary search and call the isPossible function for the every possible value of mid , and move the binary search window based on its output.\n\nwe will keep a count and iterate over the first array.\n\nNow if the current element is negative we will find all the numbers such than nums[i]*nums2[j] should be greater than x. Thus we will find the lower bound of x/nums1[i] and increase the count by n2-ind where ind is the index of largest value of nums2 which is lesser than x/nums1[i].\n\nElse if the current element is positive we will find all the numbers such that nums[i]*nums2[j] is lesser than x. thus we will find upper bound of x/nums1[i] and increase the count by ind.\n\nif at any point count >= k , it means this is possible value and we return true which means shift the window to the left as there are more smaller elements on the left side.\n\n# Complexity\n- Time complexity:\n$$O(nlogn)$$\n\n- Space complexity:\n$$O(1)$$\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    bool isPossible(vector<int>& nums1, vector<int>& nums2, long long k,\n                    long long x) {\n            \n            int n1 = nums1.size();\n            int n2 = nums2.size();\n            long long count = 0;\n\n            for(int i = 0; i<n1; i++){\n                if(nums1[i] < 0){\n                    long long rem = ceil((double)x/nums1[i]);\n                    int ind = lower_bound(nums2.begin(), nums2.end() , rem) -nums2.begin();\n                    count += (n2-ind);\n                }\n                else if( nums1[i] > 0) {\n                    long long rem = floor((double)x/nums1[i]);\n                    int ind = upper_bound(nums2.begin(), nums2.end(), rem) - nums2.begin();\n                    count += ind;\n                }\n                else {\n                    if(x>=0) count += n2;\n                }\n                if(count >= k) return true;\n            }\n            return count >=k;\n\n    }\n\n    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2,\n                                 long long k) {\n        long long s = -1e10;\n        long long n = nums1.size();\n        long long m = nums2.size();\n        long long e = 1e10;\n\n        long long ans = 0;\n\n        while (s <= e) {\n            long long mid = s + (e - s) / 2;\n\n            if (isPossible(nums1, nums2, k, mid)) {\n                ans = mid;\n                e = mid - 1;\n            } else\n                s = mid + 1;\n        }\n\n        return ans;\n    }\n};\n```
['Binary Search', 'C++']