l2 在二维数组中寻找数字

数组数字从左到右递增
从上到下递增

绿色是剩下查找范围， 永远是跟右上角的数字比较大小

类似

image.png

image.png

image.png

image.png

image.png

#include <iostream>
#include <stack>


//** matrix 数组
//** row 行
//** column 列
//** number 要查找的数字
bool Find(int * matrix, int rows ,int columns, int number) {
    bool found = false;
    
    
    // 算法的核心思想是从右上角往左下角查找，因为左边的数字比右边的数字小，上边的数字比下边小，所以两边同时缩小范围
    if (matrix != NULL && rows > 0 && columns > 0) {
        int row = 0;
        int column = columns - 1;
        while (row < rows && column >= 0 ) {
            if (matrix[row * columns + column] == number) { // 如果发现数字就跳出循环了
                found = true;
                break;
            } else {
                if (matrix [row * columns + column] > number) { // 比右边的数字小，则查找左边的，比右边的数字大，则这一行就不可能有要找的数字
                    column--;
                } else {
                    row++;
                }
            }
        }
        return found;
    }
    return found;
}

int main() {
    int matrix[] = {1,2,8,9,
                   2,3,9,12,
                   4,7,10,13,
                   6,8,11,15};
    
    if (Find(matrix, 4, 4, 7)) {
        printf("found\n");
    } else {
        printf("not found\n");
    }
    
    return 0;
}