搜索nxn矩陣

Question

我只是想確認我的答案，看看有沒有更快的方法。

如果有一個nxn矩陣被排序，那麼搜索它的最好方法是什麼？它的複雜程度是什麼？ - 二進制搜索行，然後二進制搜索列。 O（logn）時間。

如果存在具有排序行和未排序列的nxn矩陣，那麼搜索它的最好方法是什麼？它的複雜程度是什麼？ - 二進制搜索行，然後線性搜索列。上）。

Answer 1

定義矩陣上的排序方式並定義要搜索的內容。也許增加一個例子。

爲了使它更清楚，這是分類（1）：

1 6 
4 5 

或者是這個排序（2）：

1 4 
5 6 

而且，你是什麼意思與搜索。你想在整個矩陣（a）中找到單個值，在每行（b）中找到單個值還是在每行（c）中找到不同的值？

---

對於（1）（a）其是（每行n的搜索，一個）的n * log（n）的

對於（2）（a）其是log（N）（圖它作爲一個大的行，所以日誌（N * N）=>的log（n^2）=> 2 *的log（n）=>的log（n）

---

對於（1）（b）有（n）

對於（2）（b）是log 10

---

對於（1）（c）其是（每行n的搜索，一個）的n * log（n）的

對於（2）（c）其是至少n *的log（n） ，但可能你可以在值只進行排序，並使用預先分類矩陣來得到它的log（n）完成或日誌（N）*的log（n），這需要進一步的分析

---

一切都沒有證明，基於一些基本思想。