[Ninja Algorithm] Search for books from the library to matrix: Exploring efficient search in two-dimensional matrix | LeetCode Question 240 Search for two-dimensional matrix II

Find books from the library to search for matrix: Explore efficient search in two-dimensional matrices

Search strategies in life

Imagine you are looking for books in a large library. The library's bookshelf is arranged in two dimensions: each bookshelves is arranged alphabetically in the name of the book from left to right, and the top to bottom bookshelf is sorted by the year of publication. If you were looking for a specific book, what would you do? Obviously, searching one by one from the first bookshelves is the stupidest way to search. The clever way is to find the possible bookshelf (year range) first, and then quickly locate it on the bookshelf (using alphabetical order).

Problem description

LeetCode Question 240 "Search for Two-Dimensional Matrix II" describes it like this: Write a program to find a value target in a matrix of m x n. This matrix has the following characteristics:

The elements of each line are arranged ascending order from left to right
The elements of each column are arranged in ascending order from top to bottom

For example:

Input: matrix = [[1, 4, 7, 11, 15],
                 [2, 5, 8, 12, 19],
                 [3, 6, 9, 16, 22],
                 [10,13,14,17,24],
                 [18,21,23,26,30]],
 target = 5

 Output: true

The most intuitive solution: violent search

Just like searching one by one in a library, the easiest way is to iterate through each element in the matrix. Although this method guarantees an answer, it is inefficient.

Implementation of violent search

public boolean searchMatrix(int[][] matrix, int target) {
     if (matrix == null || == 0 || matrix[0].length == 0) {
         return false;
     }
    
     int m = ;
     int n = matrix[0].length;
    
     // Iterate through each element
     for (int i = 0; i < m; i++) {
         for (int j = 0; j < n; j++) {
             if (matrix[i][j] == target) {
                 return true;
             }
         }
     }
    
     return false;
 }

Optimization solution: Start searching from the upper right corner

If we look closely at the characteristics of the matrix, we can adopt a smarter approach. Just like when looking for books in the library, we can stand in a special position - the upper right corner, this position is amazing:

Looking to the left, the number will become smaller
Looking down, the numbers will get bigger

This gives us a clear search direction!

The principle of search in the upper right corner

Imagine you are playing a game of guessing numbers:

Stand in the upper right corner
If the current number is greater than the target value, move to the left (because the number below is larger, there is no need to look at it)
If the current number is smaller than the target value, move downward (because the number on the left is smaller, there is no need to look at it)
If it is equal, the answer is found

Sample run

Take the search target = 9 as an example:

1 4 7 11 [15] → larger than 9, move left
 1 4 7 [11] 15 → larger than 9, move left
 1 4 [7] 11 15 → Smaller than 9, move down
 1 4 7 11 15
 2 5 8 12 19
 3 6 [9] 16 22 → Find the target value!
 10 13 14 17 24
 18 21 23 26 30

Java code implementation

public boolean searchMatrix(int[][] matrix, int target) {
     if (matrix == null || == 0 || matrix[0].length == 0) {
         return false;
     }
    
     // Start searching from the upper right corner
     int row = 0;
     int col = matrix[0].length - 1;
    
     while (row < && col >= 0) {
         if (matrix[row][col] == target) {
             return true;
         } else if (matrix[row][col] > target) {
             // The current value is too large, move to the left
             col--;
         } else {
             // The current value is too small, move downward
             row++;
         }
     }
    
     return false;
 }

Solution comparison

Let's compare these two methods:

Violent search:

Time complexity: O(m×n)
Space complexity: O(1)
Advantages: Simple and intuitive, easy to implement
Disadvantages: No matrix characteristics, low efficiency

Search in the upper right corner:

Time complexity: O(m+n)
Space complexity: O(1)
Advantages: Make full use of matrix characteristics, efficient and fast
Disadvantages: Need to understand the sorting characteristics of the matrix

Summary of practical skills

Key points to solve matrix search problem:

Observe the characteristics of the matrix (such as sorting rules)
Find a special location (such as the upper right corner) as the starting point
Use sorting characteristics to determine the search direction
Correctly handle boundary conditions

summary

By searching for two-dimensional matrix, we learned how to search efficiently in ordered matrices. This way of thinking can not only solve algorithm problems, but also be used in database index design, image processing and other fields. Remember, when encountering problems that require searching in ordered data structures, you can consider leveraging the orderliness of the data to optimize the search process, which can usually achieve better performance than brute force search!

Author: Ninja Algorithm
Official account: Ninja Algorithm

I have prepared a list of questions to practice and detailed questions for these questions, covering most common interview questions. I can say responsibly that as long as you truly master these questions, 80% of the algorithm interviews will encounter similar questions. Reply to the official account [Question List] to obtain ~