[C] Binary search, explanation with examples
The idea is to use binary search on the answer.\nWe are searching for the least x, such that there are at least k products less than or equal to x.\n\nFor each 
The idea is to use binary search on the answer.\nWe are searching for the least x, such that there are at least k products less than or equal to x.\n\nFor each element in the array *a[n]* we perform a special binary search on the array *b[m]*, hence a total running time of *O(n.log(m).log(Range))*.\nSince the order of *a* and *b* is irrelevant, this bound can further be improved to *O(min(n,m).log(max(n,m)).log(Range))*.\n\n*How exactly do we perform the search?*\n\nLet *the upper-bound of y* be the number of elements in *b* that are less than or equal to y.\n\nLet x\u22650. Let w>0 be an element of *a* and we want to know how many products of w with an element of *b* are less than or equal to x.\nThe numbers of these products is exactly *the upper-bound of (x div w)*, for instance:\n\nx=31, w=10, b=[-5, -4, -3, -3, -2, -1, 2, 3, 3, 4, 6, 12, 13].\nThe number of products, less than or equal to 31 is 9.\nThis corresponds to the range [-5, -4, -3, -3, -2, -1, 2, 3, 3], which directly corresponds to *the upper-bound of 3*.\n\nIn case w<0 we are interested in *m - the upper-bound of (x div w)-1*.\nFor instance x=31, w=-10 in the above example.\nThe valid range of products is [-3, -3, -2, -1, 2, 3, 3, 4, 6, 12, 13].\nThe number of elemets here is exactly *m - the upper-bound of -4*, since the later corresponds to the remaining range [-5, -4].\n\nIn case x<0, we have some special cases, depending on whether w divides x or not.\n\nFor w>0 and w divides x we are again searching for *the upper-bound of (x div w)*.\nFor instance x=-30, w=10 in the above example.\nThe valid range is [-5, -4, -3, -3], which corresponds to the products [-50, -40, -30, -30], all less than or equal to -30.\n\nHowever if w does not divide x we are searching for *the upper-bound of (x div w)-1*.\nFor instance x=-31, w=10. \nThe valid range is now [-5, -4], which corresponds to the producuts [-50, -40].\nNote that -3 is no longer in the valid range, since -30 > -31.\n\nFor w<0 and w divides x we are again searching for *m - the upper-bound of (x div w)-1*.\nFor instance x=-30, w=-10. \nThe valid range is now [3, 3, 4, 6, 12, 13], which corresponds to the products [-30, -30, -40, -60, -120, -130], all less than or equal to -30.\n\nHowever if w does not divide x we are searching for *m - the upper-bound of (x div w)*.\nFor instance x=-31, w=-10.\nThe valid range is now [4, 6, 12, 13], which corresponds to the products [-40, -60, -120, -130].\nNote that 3 is now longer in the valid range, since -30 > -31.\n\nThe last remaining case is w=0, which is trivial, since all resulting products are equal to 0.\nIn case x\u22650, we have m products less than or equal to x and in case x<0 we have no such products.\n\nThe following C solution is a straight-forward illustration of the above idea.\n```\nint ub(int* a, int l, int r, long long x){\n    int m;\n    while (l <= r){\n        m = (l+r)/2;\n        if (a[m] <= x) l = m+1;\n        else r = m-1;\n    }\n    \n    return l;\n}\n\nlong long kthSmallestProduct(int* a, int n, int* b, int m, long long k){\n    long long r = (long long)(1e10), l = -r, x, c;\n    \n    int i;\n    \n    while (l <= r){\n        x = (l+r)/2;\n        \n        c = 0;\n        for (i = 0; i < n; i++){\n            if (a[i] > 0) c += ub(b, 0, m-1, x/a[i] - (x<0 && x%a[i]));\n            else if (a[i] < 0) c += m - ub(b, 0, m-1, x/a[i] - !(x<0 && x%a[i]));\n            else if (x >= 0) c += m;\n            \n            if (c > k-1) break;\n        }\n        \n        if (c <= k-1) l = x+1;\n        else r = x-1;\n    }\n    \n    return l;\n}\n```
[]