我一直在寻找对排序矩阵使用二进制搜索逻辑的最佳优化方式。
使用 Stack Over 流程中“Michal Sznajder”建议的逻辑。 Most efficient way to search a sorted matrix?
但是在计算具有递归关系的时间复杂度时存在困难。 有人可以帮助我吗。
虽然我使用的是二进制搜索逻辑，但我假设它不是 T(n) = log (m + n)。
是 T(n) = log (log (log (m x n))) 还是 log (log (m x n))？
代码可能不是最好的标准或优化但我刚开始写。
/*
1, 4, 7, 10, 13,
2, 5, 8, 11, 14,
3, 6, 9, 12, 15,
16, 17, 18, 19, 20,
21, 22, 23, 24, 25,
26, 27, 28, 29, 30
a ..... b ..... c
. . . . .
. 1 . 2 .
. . . . .
d ..... e ..... f
. . . . .
. 3 . 4 .
. . . . .
g ..... h ..... i
a, c, g < i --> if not there is no element
a, b, d < e
b, c, e < f
d, e, g < h
e, f, h < i
Left Top : Right Top
-----------Mid--------------
Left Bottom : Right Bottom
*/
public int SearchSortedMatrixInLogNByM(int[,] SortedMatix, int elementToSearch, int rowStPos, int colStPos, int rowEndPos, int colEndPos)
{
// Step 0. Check for basic validations.
if (SortedMatix == null)
{
throw new Exception("Matrix is empty");
}
// Step 1. Use divide and conquer and to get the middle element.
int resultNode = 0;
int rowMidPos = (rowStPos + rowEndPos) / 2;
int colMidPos = (colStPos + colEndPos) / 2;
// Step 2. Mid element in Recursive Sub Matrix. For e.g in above example if it is 'e', 'f','h','i' then found.
if (SortedMatix[rowMidPos, colMidPos] == elementToSearch || SortedMatix[rowMidPos, colEndPos] == elementToSearch ||
SortedMatix[rowEndPos, colMidPos] == elementToSearch || SortedMatix[rowEndPos, colEndPos] == elementToSearch)
{
return elementToSearch;
}
// Step 3. Terminate the sub matrix iteration when the element is not found in the 2 X 2 matrix.
if ((rowStPos == rowMidPos || colStPos == colMidPos) && SortedMatix[rowStPos, colStPos] != elementToSearch)
{
return 0;
}
// Step 4. Left Top Sub Matrix.
if (resultNode == 0 && elementToSearch < SortedMatix[rowMidPos, colMidPos])
{
resultNode = SearchSortedMatrixInLogNByM(SortedMatix, elementToSearch, rowStPos, colStPos, rowMidPos, colMidPos);
}
// Step 5. Right Top Sub Matrix.
if (resultNode == 0 && elementToSearch < SortedMatix[rowMidPos, colEndPos])
{
resultNode = SearchSortedMatrixInLogNByM(SortedMatix, elementToSearch, rowStPos, colMidPos, rowMidPos, colEndPos);
}
// Step 6. Left bottom Sub Matrix.
if (resultNode == 0 && elementToSearch < SortedMatix[rowEndPos, colMidPos])
{
resultNode = SearchSortedMatrixInLogNByM(SortedMatix, elementToSearch, rowMidPos, colStPos, rowEndPos, colMidPos);
}
// Step 7. Right bottom Sub Matrix.
if (resultNode == 0 && elementToSearch < SortedMatix[rowEndPos, colEndPos])
{
resultNode = SearchSortedMatrixInLogNByM(SortedMatix, elementToSearch, rowMidPos, colMidPos, rowEndPos, colEndPos);
}
return resultNode;
}
public void SearchSortedMatrixTest()
{
int[,] SortedMatix = {{ 1, 4, 7, 10, 13,},
{ 2, 5, 8, 11, 14,},
{ 3, 6, 9, 12, 15,},
{ 16, 17, 18, 19, 20,},
{ 21, 22, 23, 24, 25,},
{ 26, 27, 28, 29, 30}};
//SearchSortedMatrixInNLogN(AssendMatix, 21);
StringBuilder strBldr = new StringBuilder();
strBldr.Append("\n 1 : " + SearchSortedMatrixInLogNByM(SortedMatix, 1, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 2 : " + SearchSortedMatrixInLogNByM(SortedMatix, 2, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 3 : " + SearchSortedMatrixInLogNByM(SortedMatix, 3, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 4 : " + SearchSortedMatrixInLogNByM(SortedMatix, 4, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 5 : " + SearchSortedMatrixInLogNByM(SortedMatix, 5, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 6 : " + SearchSortedMatrixInLogNByM(SortedMatix, 6, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 7 : " + SearchSortedMatrixInLogNByM(SortedMatix, 7, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 8 : " + SearchSortedMatrixInLogNByM(SortedMatix, 8, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 9 : " + SearchSortedMatrixInLogNByM(SortedMatix, 9, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 10 : " + SearchSortedMatrixInLogNByM(SortedMatix, 10, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 11 : " + SearchSortedMatrixInLogNByM(SortedMatix, 11, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 12 : " + SearchSortedMatrixInLogNByM(SortedMatix, 12, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 13 : " + SearchSortedMatrixInLogNByM(SortedMatix, 13, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 14 : " + SearchSortedMatrixInLogNByM(SortedMatix, 14, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 15 : " + SearchSortedMatrixInLogNByM(SortedMatix, 15, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 16 : " + SearchSortedMatrixInLogNByM(SortedMatix, 16, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 17 : " + SearchSortedMatrixInLogNByM(SortedMatix, 17, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 18 : " + SearchSortedMatrixInLogNByM(SortedMatix, 18, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 19 : " + SearchSortedMatrixInLogNByM(SortedMatix, 19, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 20 : " + SearchSortedMatrixInLogNByM(SortedMatix, 20, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 21 : " + SearchSortedMatrixInLogNByM(SortedMatix, 21, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 22 : " + SearchSortedMatrixInLogNByM(SortedMatix, 22, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 23 : " + SearchSortedMatrixInLogNByM(SortedMatix, 23, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 24 : " + SearchSortedMatrixInLogNByM(SortedMatix, 24, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 25 : " + SearchSortedMatrixInLogNByM(SortedMatix, 25, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 26 : " + SearchSortedMatrixInLogNByM(SortedMatix, 26, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 27 : " + SearchSortedMatrixInLogNByM(SortedMatix, 27, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 28 : " + SearchSortedMatrixInLogNByM(SortedMatix, 28, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 29 : " + SearchSortedMatrixInLogNByM(SortedMatix, 29, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 30 : " + SearchSortedMatrixInLogNByM(SortedMatix, 30, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n\n Example 2:\n");
SortedMatix = new int[,] {{ 1, 4, 7,},
{ 2, 5, 8,},
{ 3, 6, 9}};
strBldr.Append("\n 1 : " + SearchSortedMatrixInLogNByM(SortedMatix, 1, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 2 : " + SearchSortedMatrixInLogNByM(SortedMatix, 2, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 3 : " + SearchSortedMatrixInLogNByM(SortedMatix, 3, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 4 : " + SearchSortedMatrixInLogNByM(SortedMatix, 4, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 5 : " + SearchSortedMatrixInLogNByM(SortedMatix, 5, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 6 : " + SearchSortedMatrixInLogNByM(SortedMatix, 6, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 7 : " + SearchSortedMatrixInLogNByM(SortedMatix, 7, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 8 : " + SearchSortedMatrixInLogNByM(SortedMatix, 8, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
strBldr.Append("\n 9 : " + SearchSortedMatrixInLogNByM(SortedMatix, 9, 0, 0, SortedMatix.GetLength(0) - 1, SortedMatix.GetLength(1) - 1));
MessageBox.Show("Element(s) Search in Sorted Matrix and the result(s) are " + strBldr.ToString());
}
最佳答案
更新:在 Web 的帮助下，我对上一个答案做了一些改进。
事实证明，与许多问题一样，这个问题很容易通过良好的 Google 搜索解决(只要它可以解决)。我试过“按行和列排序的搜索矩阵”。结果之一是这个页面:
Find number in sorted matrix (Rows n Columns) in O(log n)
坏消息是，在最坏的情况下，你不能比天真的一次一行的算法做得更好，该算法是 O(min(m,n) * log(max(m ,n))).另一方面，朴素算法易于实现，并且(我认为)在最佳常数因子内。
对该问题的解决方案的评论链接到包含一些其他有用 Material 的页面，http://twistedoakstudios.com/blog/Post5365_searching-a-sorted-matrix-faster ，它似乎概述了一个有用的、不那么天真的算法。我不认为我能做得更好；当然不容易。
对于它的值(value)，这是我之前的回答:
算法需要改进。考虑这个 4x4 矩阵:
1, 2, 4, 10
3, 6, 7, 12
5, 8, 9, 14
11, 13, 15, 16
考虑在该矩阵中搜索包含值 9、10 或 11 的单元格。所有这三个值都通过了子矩阵 2 中的“测试”(右上角)，但它们也都通过了子矩阵中的测试3(左下角)。事实上，其中一个在子矩阵 2 中，一个在子矩阵 3 中，一个不在这两个子矩阵中。根据包含值 4、12、13 和 16 的单元格的观察值，关于这三个数字中的任何一个，你唯一可以说的是这些数字都不在子矩阵 1 中。所以你消除了 1/4该步骤的矩阵。
值4和5按照算法应该出现在子矩阵1中(因为每个都小于6，在那个子矩阵的右下角)，但实际上一个在子矩阵2中，另一个在子矩阵中子矩阵 3。当您要查找的值小于子矩阵 1 右下角的元素时，这四个比较通常不允许您消除任何子矩阵。
关于algorithm - 想在对排序矩阵使用二进制搜索逻辑时了解时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23875945/