LeetCode 378. Kth Smallest Element in a Sorted Matrix
題目連結 http://tinyurl.com/y8sc949p
Given a n x n matrix where each of the rows and columns are sorted in
ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth
distinct element.
Example:
matrix = [[ 1, 5, 9],
[10,11,13],
[12,13,15]]
k = 8
return 13
目前正在研究用binary search解這題 http://tinyurl.com/ybqw4ubd
YUANGAO1023提到的Solution 2: Binary Search
大致的結構我都看懂了
但是不懂的是為什麼是在while迴圈的最後
是else hi = mid; 而不是 else hi = mid - 1;
我有自己代數字實際跑一遍， else hi = mid; 是正確的，但是卻不知道為什麼這是正確
也不懂為什麼 hi = mid - 1就不行
謝謝

應該可以寫 if (count > k) hi = mid - 1 else lo = mid在 sorted matrix 找中位數的問題 以前在版上有討論過#1KF5PfAs

在第三行有個註解：[lo, hi)，如果hi = mid - 1，搜索的區間就會變成[lo, hi]，這樣會出問題。可以仔細思考看看，他最後為什麼是return lo，如果搜索的區間變成[lo, hi]，那最後會無法確定答案是哪一個。在做二分搜的時候，通常都不會包含終點，就是這個原因這個題目我沒有仔細地研究，只是聊聊我對二分搜的一些理解有錯還請不吝指正嗯...其實我也不太懂他的寫法，我自己寫的話，while迴圈內只要三行就可以搞定，我晚點再來想想該怎麼解釋比較好。

if有判斷mid等於則high就是mid-1，因為mid已經不是了。