搜索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），这需要进一步的分析

---

一切都没有证明，基于一些基本思想。