算法：搜索二維整數數組中的整數的有效方法？

Question

可能顯示的文件：
Given a 2d array sorted in increasing order from left to right and top to bottom, what is the best way to search for a target number?
Search a sorted 2D matrix

甲時間效率的程序，找出在二維矩陣的元素，行和列，其中的單調遞增。 （行和列從上到下和從左到右增加）。

我只能想到二進制搜索，如果二維數組排序。

Answer 1

我提出這個問題，因爲功課上學期，和兩個學生，我曾認爲是平均，通過想出一個非常優雅的，簡單的，（可能）優化算法出乎我的意料：

Find(k, tab, x, y) 
    let m = tab[x][y] 

    if k = m then return "Found" 
    else if k > m then 
    return Find(k, tab, x, y + 1) 
    else 
    return Find(k, tab, x - 1, y) 

該算法在每次調用時都會消除一行或一列（注意它是尾遞歸的，並且可以轉換爲循環，從而避免遞歸調用）。因此，如果你的矩陣是n * m，算法在O（n + m）中執行。這個解決方案比二分搜索分拆更好（當我解決這個問題時，我期待解決方案）。我修正了一個錯字（k在遞歸調用中變成了x），並且，正如Chris所指出的，這應該最初用「右上角」來調用，即Find（k，tab， n，1），其中n是行數。

Answer 2

假設我讀得對，你說第n行的底部總是小於第n + 1行的頂部。如果是這種情況，那麼我會說最簡單的方法是搜索第一行使用二進制搜索的數字或下一個最小的數字。然後，您將識別出所在的列。然後對該列進行二進制搜索，直至找到它。

Answer 3

由於行和列單調遞增的，你可以這樣做一個整潔的小搜索：

開始在左下角。如果您正在查找的元素大於該位置的元素，則向右。如果不那麼上去。重複，直到找到該元素或您碰到一個邊緣。示例（十六進制進行格式化更容易）：

1 2 5 6 7 
3 4 6 7 8 
5 7 8 9 A 
7 A C D E 

讓我們尋找8.開始在位置（0,3）：7 8> 7，所以我們去的權利。我們現在在（1，3）：A。8 < A，所以我們走了。在（1，2）：7，8> 7，所以我們走對了。 （2,2）：8 - > 8 == 8所以我們完成了。

你會發現然而，這僅發現其價值的要素之一是8

編輯，萬一這一點不明確這個運行在O（N + M）平均和最差案件時間。

Answer 4

開始在（0,0）

• 而值太低，繼續向右側（0,1），然後（0,2）等。
• 達到值過高時，下去一個，左一個（1,1）

重複這些步驟應該把你的目標。