Algorithm design to search a value in matrix [duplicate]

This question already has answers here: How do I search for a number in a 2d array sorted left to right and top to bottom? (21 answers) Closed 5 years ago.

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 el开发者_如何学Cement < 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

---

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

1. If the current value is smaller than the value you're searching for, go right.
2. If the current value is larger than the value you're searching for, go up.
3. If the current value is equal to what you're searching for, return true.
4. 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.

---

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.