• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

## In an N * m two-dimensional array, each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Perform an efficient function that takes such a two-dimensional array and an integer and determines whether the integer is in the array.

  • Example:
Existing matrix matrix is as follows: [[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]]Copy the code
  • Given target = 5, return true.
  • Given target = 20, return false.

Train of thought

  • Because it’s a special two-dimensional array, our original idea of violence must be optimized
    • Look at the specificity of two-dimensional arrays
    • It’s an ascending left to right, and ascending top to bottom
    • So we can use it because it’s orderedBinary searchTo solve the
    • Constantly changing the number of rows and columns will definitely save you time to search
    • So by putting these ideas together, you write the following code
class Solution {
    public boolean findNumberIn2DArray(int[][] a, int target) {
        if (a == null || a.length == 0) return false;

        int m = a.length;  M is the length of a two-dimensional array line
        int n = a[0].length; // n is the length of a two-dimensional array column
        int row = 0;
        int column = n-1;
        
        while (row < m && column >= 0) {
            if (target < a[row][column]) {
                // When the target number is less than the current number, the column is moved down one bit
                column--;   
            }else if (target > a[row][column]) {
                // When the target number is less than the current number, the row moves to the right one bit
                row++;
            }else {
                return true; }}return false; }}Copy the code