C++ implements search in two-dimensional array

Today the editor saw a small question on the Internet, which is about searching in a two-dimensional array. I will take you to learn it together. If you are interested, take a good look. The code is attached and you can imitate it and write it!

Question:

In a two-dimensional array, each row is sorted in increasing order from left to right. Each column is sorted in ascending order from top to bottom. Please complete a function, input such a two-dimensional array and an integer, and determine whether the array contains the integer.

1. Ideas

First select the number in the upper right corner of the array. If the number is equal to the number you are looking for, the search process ends; if the number is greater than the array you are looking for, remove the column where the number is located; if the number is less than the number you are looking for, remove the row where the number is located. That is to say, if the number to be found is not in the upper right corner of the array, one row or column will be eliminated from the search range of the array each time, so that the search range can be narrowed at each step until the number to be found is found, or the search range is null.

2. Example

If the number 7 is found in a two-dimensional array, it will return true. If it is not found, it will return false.

1 2 8 9

2 4 9 12

4 7 10 13

6 8 11 15

The search process is as follows:

3. Programming implementation

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int rows = array.size();
        int cols = array[0].size();
        if(!array.empty() && rows > 0 && cols > 0){
            int row = 0;
            int col = cols - 1;
            while(row < rows && col >= 0){
                if(array[row][col] == target){
                    return true;
                }
                else if(array[row][col] > target){
                    --col;
                }
                else{
                    ++row;
                }
            }
        }
        return false;
    }
};

[Recommended courses: C Video Tutorial]

The above is the detailed content of C++ implements search in two-dimensional array. For more information, please follow other related articles on the PHP Chinese website!