Algorithm design to search a value in matrix

Question

This question is not a homework, it is just out of personal interest and mainly my curiosity

My professor talked about this question for a little while during class, but he didn't talk much about this. And below is the question:

Given an m x n matrix A whose integer elements are sorted along the horizontal and vertical direction respectively. I need to develop a recursive program to search if a query value a is in A. Discuss the time complexity of your design.

So I thought about this for a while. My first approach is to check the base case: the first element and last element

check if first element > item check if last element < item

item is what I want to find

This is the imaginary matrix: ( x can be any number, but this matrix is sort vertically and horizontally)

             first     x          x        x         x
                 x     x          x        x         x
                 x     x         mid       x         x
                 x     x          x        x         x
                 x     x          x        x         last

After I check the base case and make sure the "item" I want to find is inside the range of this matrix, I don't know if it is alright to check from the "mid" in the matrix ( like binary search). If item < mid , then focus on left half. If item > mid, then focus on right half.

But, then I tried to make a matrix like below and my "item" is 10

                 1     2          3        4         5
                 2     4          7        8          9
                 3     6          10       11         12

If I follow the way I said before: since 10 is larger than the middle "7", I focus on right part. then I check "8", since 10 is larger than "8", I search for right part. But 10 is not in the right ...

Can anyone give me idea or insight how to solve this question? Thanks a lot

I remember the same question here, a few months ago. Try searching StackOverflow. — ypercubeᵀᴹ, May 22 '11 at 21:22
Similar question: http://stackoverflow.com/questions/3316246/search-a-sorted-2d-matrix — ypercubeᵀᴹ, May 22 '11 at 21:27
And a related question (but not the same): http://stackoverflow.com/questions/5000836/selection-algorithms-on-sorted-matrix — ypercubeᵀᴹ, May 22 '11 at 21:28
@ypercube - oh thanks a lot. I love the answer from the first link, which divides the whole matrix into 4 quarters. — Hold_My_Anger, May 22 '11 at 21:54

score 5 · Accepted Answer · answered May 22 '11 at 21:25

Start at the lower left corner (the one with 3 in it in your example).

If the current value is smaller than the value you're searching for, go right.
If the current value is larger than the value you're searching for, go up.
If the current value is equal to what you're searching for, return true.
If you went outside of the matrix, return false.

This is O(n + m), where n and m are the number of lines and columns in your matrix. This is because at each step, you completely rule out an entire row or column.

ninjagecko · Answer 2 · 2011-05-22T21:54:12.533

Best solution time-wise is O(1) and is to just keep track of which elements are in the matrix using a hash table. Could also use a Bloom filter if space is an issue.

However because they're sorted, it may not be worth adding all the machinery.

The solution the problem is looking for I think is an O(N) solution (where the matrix is size NxN); where you proceed from the top-left to bottom-left to bottom-right until you find an element larger than your query. Then you search the "level curve" by squirming towards the top-right, each time performing a comparison to see if you've overshot or undershot your query (going right or up depending).

Another way you can think about this is keeping track of the window lower_c < query < higher_c for each column c, going left to right. This window is always of size 2.

@ypercube: yes, it is subsumed into reading the matrix (or loading it into memory, however you want to think about it) — ninjagecko, May 22 '11 at 21:38

Algorithm design to search a value in matrix

2 Answers2