Want to know Time Complexity while using Binary Search logic for Sorted Matrix

Question

I was looking for best optimized way of using Binary Search logic for Sorted Matrix.

Used the logic suggested by "Michal Sznajder" from Stack Over flow. Most efficient way to search a sorted matrix?

But having difficultly in calculation Time complexity with recurrence relation. Can someone can plz help me.

Though I am using binary search logic, I assume it is not T(n) = log (m + n).

Is it T(n) = log (log ( log (m x n))) or log ( log (m x n)) ?

The code may not be the best standard or optimized but I just started writing.

/*
 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());          
}

Before you ask for time complexity, make sure the algorithm is correct. Yes, an algorithm was posted in response to http://stackoverflow.com/questions/4137986/most-efficient-way-to-search-a-sorted-matrix/4138854#4138854 but the comments on that answer indicate that the algorithm is incomplete. It will give wrong answers under some circumstances. — David K, May 26 '14 at 19:05
Yes David. I read those comments and I have taken care few condition in my logic. May be I could have mention that in my description. E.g. I am checking for resultNode not to be zero to make anther sub matrix recursive call. Tested with most conditions but not posted all of them here. One point I yet to consider for optimization is from my e.g. If I look for 3, in sub matrix (1,4,2,5) it will first compare with 1,2,4 as 3 is less than 5. It would make more un-necessary check if (1,4,2,5) and 3 are in lakh rows in some X million matrix. Thank you for highlighting. — Sai, May 26 '14 at 19:26
One simplest way many of us aware is, If the matrix is n (columns) X m (rows) and n > m. Then repeat loop linearly for m (rows) and apply binary search on n (columns). So it would be O(m log n). But I was trying for the one. — Sai, May 26 '14 at 19:55

DanLatimer · Answer 1 · 2014-05-26T18:50:09.947

1

If I understand the algorithm correctly you are dividing your matrix into four quadrants using the Z pattern and then querying by recursively checking the center of a quadrant and knowing which of its four sub-quadrants to look in next.

In this case you can think of it similarly to a tree structure where each node has four children. Each time you evaluate the current node you will move into one of the four subnodes. The time to query the location of a node in such a tree structure (and this data structure) would be O(log base 4 (n)) where n is the total number of elements in your matrix.

The reason for this is because that is the height of the tree and we must stop on each level of the tree only once to find our element which is most likely at the bottom since that level of the tree holds ~75% of the nodes in the entire tree.

Of course that is for a square matrix. As the matrix becomes more rectangular your search becomes less efficient with the worst case scenario being a matrix of n x 1 which would just be a long line. In that case you would see O(log base 2 (n)) as you are really only splitting between two sub-nodes each time.

edited May 26 '14 at 18:50

answered May 26 '14 at 18:44

DanLatimer

117
8

Wow thanks for quick response and nice example with respect to tree. Good to know this. In the same simple way will you be able to help me with calculating with Recurrence Relation too? – Sai May 26 '14 at 18:57
I'm not familiar with the term Recurrence Relation, what exactly are you looking for? – DanLatimer May 26 '14 at 19:07
Not so fast! See my comment on the main question. – David K May 26 '14 at 19:08
@DanLatimer. No problem, Recurrence Relation is one of the method used to calculate the time efficiency of recursion methods, and another popular type is master theorem. http://en.wikipedia.org/wiki/Recursion_(computer_science)#Time-efficiency_of_recursive_algorithms – Sai May 26 '14 at 19:35
1

I don't have enough "reputation points" to comment on David K's answer below, but the problem with it is that his example no longer satisfies the Z pattern and therefor would not be searchable by this method. AKA [Morton Order](http://en.wikipedia.org/wiki/Z-order_curve) – DanLatimer May 26 '14 at 19:53
1

I don't see any mention of a Z pattern in either of the question statements. Merely that the columns and rows each individually satisfy the sorting condition. Moreover, I am not even the person who pointed out the flaw in the original algorithm. – David K May 26 '14 at 20:47

score 1 · Accepted Answer · edited May 23 '17 at 11:57

Update: I was able to improve on my last answer a little, with a little help from the Web.

It turns out that like many problems, this one is readily solved (insofar as it can be solved) by means of a good Google search. I tried "search matrix sorted by row and column". One of the results was this page:

Find number in sorted matrix (Rows n Columns) in O(log n)

The bad news is that in the worst case, you can't do much better than a naïve one-line-at-a-time algorithm, which is O(min(m,n) * log(max(m,n))). On the other hand, the naive algorithm is easy to implement and (I think) within a constant factor of optimal.

A comment on the solution to that question links to a page with some additional useful material, http://twistedoakstudios.com/blog/Post5365_searching-a-sorted-matrix-faster, which appears to outline a useful, less naïve algorithm. I don't think I can do better than that; certainly not easily.

For what it's worth, here's my previous answer:

The algorithm needs work. Consider this 4x4 matrix:

 1,  2,  4, 10
 3,  6,  7, 12
 5,  8,  9, 14
11, 13, 15, 16

Consider searching this matrix for cells containing the values 9, 10, or 11. All three of those values pass the "test" to be in submatrix 2 (upper right), but they all also pass the test to be in submatrix 3 (lower left). In fact, one of them is in submatrix 2, one is in submatrix 3, and one is in neither of those two submatrices. Really the only thing you can say about any of those three numbers based on the observed values of the cells containing the values 4, 12, 13, and 16 is that none of those numbers is in submatrix 1. So you eliminate 1/4 of the matrix at that step.

The values 4 and 5 should occur in submatrix 1 according to the algorithm (because each is less than 6, which is at the lower right corner of that submatrix), but in fact one is in submatrix 2 and the other is in submatrix 3. The four comparisons don't generally allow you to eliminate any of the submatrices when the value you're looking for is less than the lower right-hand element of submatrix 1.

I agree with you David, yes to mentioned above at main comments about one of the similar example for searching 4 from your example. By the way, Do you think of any best way to rewrite the algo? if not some clue also should be helpful along with time complexity. Thank you. — Sai, May 26 '14 at 19:46
@LearningBee : I did find some additional information that may help. I have added it to the answer above. — David K, May 27 '14 at 01:09
Thank you for your time and link David, I too come across the stack overflow link but overlooked. I appreciate your help. — Sai, May 27 '14 at 02:14

Want to know Time Complexity while using Binary Search logic for Sorted Matrix

2 Answers2