Binary Search wtih explnation JAVA
Intuition\n Describe your first thoughts on how to solve this problem. \nThe given arrays are already sorted. We need find the kth smallest product.\n\n##### Br
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe given arrays are already sorted. We need find the $$k$$th smallest product.\n\n##### Brute Force approach:\nWe can create a PriorityQueue with k Length and we can iterate each element in nums1 with each element in nums2. The product we can put in the Priority Queue. But this appraoch will take $$O( (n*m) log n)$$.\n\n##### Binary Search:\nAs the arrays are already sorted, we can use BST to find the no of products which are less than or equal to current value. This current value can vary between Long.MIN_VALUE to Long.MAX_VALUE.\n\ne.g:\n[1,2,3,4,5]\n[1,2,3,4,5]\nAll the products are \n```\n[ (1,2,3,4,5), (2,4,6,8,10), (3,6,9,12,15), (4,8,12,16,20), (5,10,15,20,25)]\n```\n\nFor the given no 8, the no of products <= 8 are :\n```\n[ (1,2,3,4,5), (2,4,6,8), (3,6), (4,8), (5)]\nAns = 5 + 4 + 2 + 2+ 1 = 14\n```\n\nSo if we have a method which gives no of products which are less than equal to given value than we can use BST as follows to solve the problem.\n\n```\nl = long.MIN_VALUE\nh = long.MAX_VALUE\nwhile(l < h)\n{\n    m = l +(h-l)/2;\n    val = getProductsLessThanOrEqualToM(m);\n    if(val >= k) h = m\n    else l = m\n}\nreturn h\n```\n\n##### How to get no of products less than given value\n\nFor simplicity lets consider both of our array only contains postive value.\n\n```\nIndex: 0,1,2,3,4\nNums1: 1,2,3,4,5\nNums2: 1,2,3,4,5\n\nWe want to get all the products less than 8\n[0, 4] -> 1 * 5 = 5 so it indicates all the index (0 to 3 also will have the product less than 8) => 5\n\n[1, 4] -> 2 * 5 = 10 which is greater than 8\n[1, 3] -> 2 * 4 = 8 which is equal to 8. So all index b/w [0,3] also will have the product less than 8 => 4\n\n//we don\'t need to consider [2,4] as [1,4] already not in the list\n[2,3] -> 3 * 4 = 12 which is greater than 8\n[2,2] -> 3 * 3 = 9  which is greater than 9\n[2,1] -> 3 * 2 = 6 so all the index b/w [0,1] have the product less than 8 => 2\n\n[3,1] -> 4 * 2 => 8 so all the index b/w [0,1] have the product less than 8 =>2\n\n[4,1] -> 5 * 2 => 10  which is greater than 8\n[4,0] -> 5 * 1 => 5 so the only 0 the index of nums2 will contibute => 1\n\nTotal ans: 5 + 4 + 2 + 2 + 1 = 14\n\n```\n\n##### How to handle postivie and negative nos?\nWhen nums1 is positive and nums2 is positive.\n\n```\n*\n1,2,3,4,5\n1,2,3,4,5\n        *\nThe start index:\nfor nums1: 0\nfor nums2: 4\n```\n\nWhen nums1 is positive and nums2 is negative.\n```\n        *\n1,2,3,4,5\n-5,-4,-3,-2,-1\n             *\nThe start index:\nfor nums1: 4\nfor nums2: 4\n```\n\nWhen nums1 is negative and nums2 is negative.\n```\n             *\n-5,-4,-3,-2,-1\n-5,-4,-3,-2,-1\n*\nThe start index:\nfor nums1: 4\nfor nums2: 0\n```\n\nWhen nums1 is negative and nums2 is positive.\n```\n*\n-5,-4,-3,-2,-1\n1,2,3,4,5\n*\nThe start index:\nfor nums1: 0\nfor nums2: 0\n```\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\nn - no of elements in the array 1\nm - no of elements in the array 2\n- Time complexity: $$O( (n+m) log n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int findMaxNegativeIndex(int[] nums)\n    {\n        var low = 0;//negtive no\n        var high = nums.length -1;//not a negative no\n        if(nums[low] > 0) return -1;//don\'t not have any negative value\n        if(nums[high] < 0) return high;//all numbers are negative\n        while(low < high)\n        {\n            var m = (low + high + 1)/2;\n            if(nums[m] < 0)\n            {\n                low = m;\n            }else{\n                if(high == m) break;\n                high = m;\n            }\n        }\n        return low;\n    }\n    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {\n        long low = Long.MIN_VALUE/2;//have less than k no product than this\n        long high = Long.MAX_VALUE/2;//have atleast k no product less than this\n        var negInd1 = findMaxNegativeIndex(nums1);\n        var negInd2 = findMaxNegativeIndex(nums2);\n        while(low < high)\n        {\n            long m = low + (high-low)/2;\n            var val = getNoOfProductLessThan(m, nums1, nums2, negInd1, negInd2);\n            if(k <= val){\n                high = m;\n            }else{\n                 if(low == m) break;\n                low = m;\n            }\n        }\n\n        return high;\n    }\n    public long getNoOfProductLessThan(long m, int[] nums1, int[] nums2, int f, int s)\n    {\n        var l1 = nums1.length;\n        var l2 = nums2.length;\n        \n        long ans = 0;\n\n        //when nums1 pos and nums2 is pos\n        var j = l2-1;\n        for(int i = f+1; i < l1; i++)\n        {\n            //special case when nums1[i] == 0\n            if(nums1[i] == 0)\n            {\n                if(m >= 0) ans+= l2;\n                continue;\n            }\n            while(j > s && ( (long)nums1[i] * (long)nums2[j] > m)  )\n            {\n                j--;\n            }\n            if(j > s) ans+= j-s;\n        }\n\n        //when nums1 pos and nums2 is neg\n        j = s;\n        for(int i = l1-1; i > f; i--)\n        {\n            if(nums1[i] == 0) break;\n            while(j >= 0 && ( (long)nums1[i] * (long)nums2[j] > m)  )\n            {\n                j--;\n            }\n            if(j >= 0) ans += (j+1);\n        }\n\n        //when nums1 neg and nums2 is neg\n        j = 0;\n        for(int i = f; i >= 0; i--)\n        {\n            while(j <= s && ( (long)nums1[i] * (long)nums2[j] > m)  )\n            {\n                j++;\n            }\n            if(j <= s) ans+= (s-j+1);\n        }\n\n        //when nums1 neg and nums2 is pos\n        j = s+1;\n        for(int i = 0; i <= f; i++)\n        {\n            while(j < l2 && ( (long)nums1[i] * (long)nums2[j] > m)  )\n            {\n                j++;\n            }\n            if(j < l2) ans += (l2 - j);\n        }\n        return ans;\n    }\n}\n```
['Java']