Hi, @zmzkee Thanks for the question. I'd better make it clear for how to use Binary Search in this qustion.

about binary search, why lo must in matrix?

In the post there is a section, it happens to fit this problem.

This snippet of code is aim to find the first x for which p(x) is true

Suppose matrix = [ [1,7], [8, 10] ] and k=2.

Using Binary Search, we should

Define the Search space: [1..10]
Design the predict: p(x) is count( (numbers in matrix) <= x ) >= k

So in the problem, we are going to find the first element x for which p(x) is true, for which count of numbers in [ [1,7], [8, 10] ] less or equal than x just >=2.

The element (lo) must be in the matrix to be the first one to make the prediction truth.

In case my code in "BINARY SEARCH (SOLUTION)" is not clear enough, I've rewritten it.

def kth_smallest(matrix, k)
lo, hi = matrix[0][0], matrix[-1][-1]
p = ->(x) {
count = 0
matrix.each do |row|
# b-searching (equals: count += row.count {|num| num <= x})
count += ( (0..row.count-1).bsearch{|i| row[i] > x } or row.count )
end
count >= k
}
while lo < hi
mid = (lo+hi)/2
if p[mid]
hi = mid
else
lo = mid + 1
end
end
return lo
end