搜索排序矩阵的最有效方法? [英] Most efficient way to search a sorted matrix?

问题描述

我分配了一个写一个算法(不是任何特定语言的，只是伪代码)，该算法接收一个矩阵[size:M x N]，该矩阵的排序方式是对所有行进行排序并且对所有它的列是单独排序的，并在此矩阵内找到某个值.我需要写出我能想到的最省时的算法.

I have an assignment to write an algorithm (not in any particular language, just pseudo-code) that receives a matrix [size: M x N] that is sorted in a way that all of it's rows are sorted and all of it's columns are sorted individually, and finds a certain value within this matrix. I need to write the most time-efficient algorithm I can think of.

矩阵看起来像:

1  3  5
4  6  8
7  9 10

我的想法是从第一行和最后一列开始，然后简单地检查该值，如果该值较大则减小，如果小于左值则继续这样做，直到找到该值或直到索引超出范围为止(如果该值不存在).该算法以线性复杂度O(m + n)工作.有人告诉我，这样做可能是对数复杂的.是否有可能?如果可以，怎么办?

My idea is to start at the first row and last column and simply check the value, if it's bigger go down and if it's smaller than go left and keep doing so until the value is found or until the indexes are out of bounds (in case the value does not exist). This algorithm works at linear complexity O(m+n). I've been told that it's possible to do so with a logarithmic complexity. Is it possible? and if so, how?

推荐答案

您的矩阵如下所示:

a ..... b ..... c
. .     . .     .
.   1   .   2   . 
.     . .     . .
d ..... e ..... f
. .     . .     .
.   3   .   4   .
.     . .     . .
g ..... h ..... i

，并具有以下属性:

a,c,g < i  
a,b,d < e
b,c,e < f
d,e,g < h
e,f,h < i

因此，在最低矩阵的最角处(例如i)的值始终是整个矩阵中的最大值 如果将矩阵分成4个相等的块，则此属性是递归的.

So value in lowest-rigth most corner (eg. i) is always the biggest in whole matrix and this property is recursive if you divide matrix into 4 equal pieces.

所以我们可以尝试使用二进制搜索:

So we could try to use binary search:

1. 追求价值，
2. 分成几部分，
3. (以某种方式)选择正确的作品，
4. 转到1个新作品.

因此算法可能如下所示:

Hence algorithm could look like this:

input: X - value to be searched
until found
 divide matrix into 4 equal pieces
 get e,f,h,i as shown on picture
 if (e or f or h or i) equals X then 
   return found
 if X < e then quarter := 1
 if X < f then quarter := 2
 if X < h then quarter := 3
 if X < i then quarter := 4
 if no quarter assigned then 
    return not_found
 make smaller matrix from chosen quarter 

对我来说，这看起来像O(log n)，其中n是矩阵中元素的数量.它是一种二分搜索法，但是在两个方面.我无法正式证明它，但类似于典型的二进制搜索.

This looks for me like a O(log n) where n is number of elements in matrix. It is kind of binary search but in two dimensions. I cannot prove it formally but resembles typical binary search.

这篇关于搜索排序矩阵的最有效方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！