**Challenge**: How to find an element in a sorted matrix where row and column values increase monotonically?

**What is a matrix? **A matrix is a table of values consisting of rows and columns. Here, we represent the matrix as a list of integer lists. Hence, we can access matrix values with the indexing and slicing notation.

Table of Contents

## How to Find an Element in a Matrix in Python?

The naive algorithm to find an element in a Python matrix is to iterate over all rows and values in that rows and compare these elements to the searched value:

def matrix_find(matrix, value): for row in matrix: for element in row: if element == value: return True return False matrix = [[3, 4, 4, 6], [6, 8, 11, 12], [6, 8, 11, 15], [9, 11, 12, 17]] print(matrix_find(matrix, 7)) # False print(matrix_find(matrix, 17)) # True

If the matrix has ** n** rows and

**columns, the runtime complexity of the algorithm is**

*m**because you have to perform*

**O(n*m)***comparisons. This is not optimal for a*

**n*m****matrix (see next)!**

*sorted*## How to Find an Element in a Sorted Matrix in Python?

**What is a sorted matrix?** The matrix is

*sorted*as the integers in the rows and columns increase monotonically with the row and column number.

The **matrix-find algorithm** is a beautiful way to search a value in a sorted matrix without visiting all values in the sorted matrix.

Here’s the algorithm:

def matrix_find(matrix, value): if not matrix or not matrix[0]: return False j = len(matrix) - 1 for row in matrix: while row[j] > value: j = j - 1 if j == -1: return False if row[j] == value: return True return False matrix = [[3, 4, 4, 6], [6, 8, 11, 12], [6, 8, 11, 15], [9, 11, 12, 17]] print(matrix_find(matrix=matrix, value=7))

The function `matrixFind`

takes a sorted integer matrix and an integer value. It returns `True`

if the matrix contains the integer value.

### Explanation

In the first few lines, the algorithm checks whether the matrix is empty and returns `False`

if this is the case.

Then, the while loop iterates over rows `i`

and column `j`

of the matrix starting with the first row `i=0`

and the last column `j=n-1`

.

But instead of searching the whole matrix, the algorithm uses a smarter strategy. It skips whole rows and columns at a time with the following method.

Check the last value of the first row (top right matrix value). We denote this value as `matrix[i][j]`

. There are three cases.

- The top right matrix value
`matrix[i][j]`

is equal to the searched value. In this case, the algorithm returns`True`

. - The top right matrix value
`matrix[i][j]`

is smaller than the searched value. Because the matrix is sorted, the top right matrix value is the largest element in the row i. Thus, we can skip row i completely by going to the next row`i = i+1`

. Next, we repeat this procedure with a smaller matrix that has one row less (i.e., row i). - The top right matrix value
`matrix[i][j]`

is larger than the searched value. This means that the whole column j has only elements that are larger than the searched value. Thus, we are sure that our searched value is not in column j and we can skip this column completely by decreasing`j = j-1`

. Next, we repeat this procedure with a smaller matrix that has one column less (i.e., row j).

### Runtime Complexity Matrix-Find

In summary, the idea of this great algorithm from Keith Schwartz reduces one row or one column in each iteration. The runtime is only `O(2n)`

instead of `O(n^2)`

for a squared matrix with n rows and columns.

### Puzzle Matrix-Find

Test your understanding by solving the following Python puzzle on our Finxter app:

Are you a master coder?

Test your skills now!

## Related Video

## Where to Go From Here?

Enough theory, let’s get some practice!

To become successful in coding, you need to get out there and solve real problems for real people. That’s how you can become a six-figure earner easily. And that’s how you polish the skills you really need in practice. After all, what’s the use of learning theory that nobody ever needs?

**Practice projects is how you sharpen your saw in coding!**

Do you want to become a code master by focusing on practical code projects that actually earn you money and solve problems for people?

Then become a Python freelance developer! It’s the best way of approaching the task of improving your Python skills—even if you are a complete beginner.

Join my free webinar “How to Build Your High-Income Skill Python” and watch how I grew my coding business online and how you can, too—from the comfort of your own home.

While working as a researcher in distributed systems, Dr. Christian Mayer found his love for teaching computer science students.

To help students reach higher levels of Python success, he founded the programming education website Finxter.com. He’s author of the popular programming book Python One-Liners (NoStarch 2020), coauthor of the Coffee Break Python series of self-published books, computer science enthusiast, freelancer, and owner of one of the top 10 largest Python blogs worldwide.

His passions are writing, reading, and coding. But his greatest passion is to serve aspiring coders through Finxter and help them to boost their skills. You can join his free email academy here.