C# Binary Search On Answer Solution
IntuitionApproachWe search between a very wide range of possible products (from
−10^10 to 10^10).
For each midpoint (mid), we count how many products are less t
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->My intuition was to convert the problem from sorting products explicitly to leveraging binary search to simulate the sorting process indirectly.
___
# Approach
<!-- Describe your approach to solving the problem. --> Binary Search (KthSmallestProduct):
We search between a very wide range of possible products (from 
−10^10 to 10^10).
For each midpoint (mid), we count how many products are less than or equal to mid using CountLessOrEqual.
Counting Products (CountLessOrEqual):
For each element in nums1, we count the number of elements in nums2 that can form a product less than or equal to mid.
Split into CountPositive (when num1 >= 0) and CountNegative (when num1 < 0).
Efficient Counting (CountPositive and CountNegative):
Use binary search to quickly count the number of valid products in nums2 for a given value of nums1[i].
___
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->O(m * log*(n)).
___
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->O(1).
___
# Code
```csharp []
public class Solution {
    public long KthSmallestProduct(int[] nums1, int[] nums2, long k) {
        long left = -10000000000L; // Smallest possible product
        long right = 10000000000L; // Largest possible product
        
        while (left < right) {
            long mid = left + (right - left) / 2;
            if (CountLessOrEqual(nums1, nums2, mid) >= k) {
                right = mid; // Narrow down to smaller range
            } else {
                left = mid + 1; // Narrow down to larger range
            }
        }
        
        return left;
    }
    
    private long CountLessOrEqual(int[] nums1, int[] nums2, long target) {
        long count = 0;
        foreach (int num1 in nums1) {
            if (num1 >= 0) {
                count += CountPositive(nums2, num1, target);
            } else {
                count += CountNegative(nums2, num1, target);
            }
        }
        return count;
    }
    
    private long CountPositive(int[] nums, int num, long target) {
        int low = 0, high = nums.Length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if ((long)num * nums[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }
    
    private long CountNegative(int[] nums, int num, long target) {
        int low = 0, high = nums.Length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if ((long)num * nums[mid] <= target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return nums.Length - low;
    }
}
```
['Array', 'Binary Search', 'C#']