這一題要怎麼解？我用2個二分搜尋但是一直WA(33%)，這一題有其他解法嗎？還是有什麼特殊的情況？

還有目前484只有我沒過qq

雙重二分確實可以得到所求，但問題是兩層二分各自所扮演的角色。

可否請您陳述一下您二分的條件或是它們做的事呢？

第一個二分我是寫在(-10000)*n ~ 2*n*n + 2*n 之間搜尋一個數使得矩陣內有m-1個數字小於他。

然後第二個二分是用來判斷矩陣中有幾個小於他的元素，就是先列舉 i 然後再二分搜 j 的值，因為 j (固定 i )似乎是遞增的。

然後找到數之後考慮它不在矩陣內的可能性，用第二個二分稍作修改，找到離他最近又大於他的元素就是答案。

我試過用暴力解比對n = 1~200都沒問題，而且我有修改過使得相同的數不會並排(這麼做讓掛掉的點稍微前進了一點)

據我的理解，這兩個二分最後收束到的值正好會在矩陣裡（剛好就是第 M 小的）。

當然，這也要看第二個二分怎麼寫。

如果第一個二分的上界下修之條件為第二個二分統計出有 > M 個大於目前中間值（第一二分上界與下界之平均），而不是有 ≧ M 個的話，結果就不會是上面這樣……應該吧。

喔喔我找到問題了 :)

我把答案的指派設置在他偵測到剛好有m-1個數小於他的時候，但是其實二分搜收束的答案不見得會計算出m-1個因為會有複數個相同數字。

總之感謝拉!!

關於這題的二分法收斂的逼近方式，我看過的程式碼有兩個類型：

(1) 從選擇的範圍內不斷縮減直到『沒有數字可以選擇』＝左右邊界內交叉，

     所以邊界調整方式是根據猜的結果調整：(1)左邊界＝猜測值+1 或是 (2)右邊界＝猜測值-1

     過程中只有當判斷式 return true 時才需要更新答案，最後更新的就直接輸出即可。

     具體的程式碼 和 解題想法可以參照 inversion 在個人部落客的文章 ZeroJudge - e894: 第 M 小數　解題心得。

(2) 從選擇的範圍內不斷縮減直到『剩下一個數字』＝左右邊界交接於同一個數字

     以這題為例判斷式同(1)，但調整方式為：(1)左邊界＝猜測值+1 或是 (2)右邊界＝猜測值

     注意到：右邊界比起(1) 少了-1，因為該數字是 #矩陣中小於猜測值的數字個數 ≥ Ｍ中最小值，

     正確答案是剩下的唯一數字-1，是因為答案存在該矩陣中(廢話...) 故 #矩陣中小於猜測值的數字個數 ≤ Ｍ-1。

     我們可以注意到收斂的前一刻：左右邊界值必定差1，而猜測值是兩值取平均後的捨位。

     正數時猜測值＝左邊界，根據判斷式討論：不符合則左邊界更新和右邊界相同，符合判斷式則右邊界更新和左邊界相同，必定收斂。

     負數時猜測值＝右邊界，根據判斷式討論：不符合則左邊界更新和右邊界相同，符合判斷式則右邊界和上一次一樣＝無法收斂。

     https://www.codepile.net/pile/Z93eqr1l