LeetCode 668. 乘法表中第k小的数（二分查找）

例 1：
输入: m = 3, n = 3, k = 5
输出: 3
解释: 
乘法表:
1	2	3
2	4	6
3	6	9
第5小的数字是 3 (1, 2, 2, 3, 3).

例 2：
输入: m = 2, n = 3, k = 6
输出: 6
解释: 
乘法表:
1	2	3
2	4	6
第6小的数字是 6 (1, 2, 2, 3, 4, 6).

注意：
m 和 n 的范围在 [1, 30000] 之间。
k 的范围在 [1, m * n] 之间。

class Solution {
public:
    int findKthNumber(int m, int n, int k) {
        int l = 1, r = m*n, mid, ans;
        while(l <= r)
        {
            mid = l+((r-l)>>1);
            if(ok(m,n,mid,k))
            {   //选取数字为mid时，有 >= k 个数 <= mid
                ans = mid;
                r = mid-1;
            }
            else
                l = mid+1;
        }
        return ans;
    }
    bool ok(int m, int n, int mid, int k) 
    {   // 检查每一行，<= mid 的数，共计有多少个
        int count = 0;
        for(int i = 1; i <= m; i++)
        {
            count += min(mid/i, n);
        } //每行最多有n个数小于 mid，开始没注意，错误一发
        return count >= k;//有count 个数 <= mid
    }
};