题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否还有该整数。

例如下面的二维数组就是每行，每列都递增排序。如果这个数组中查找数字7，则返回true；如果查找数字5 由于数组不含有该数字，则返回false。
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
这个问题的关键是要反向思考，我最早是想着从左到右的比较，虽然也想着一排一排的剔除，但是从右向左剔除更简单一些。

思路

下面是我用不同种语言写的代码，已经献上了我的膝盖

C++

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;
}

Object-C

-(BOOL)FindNumber:(NSArray *)matrix rows:(int)rows columns:(int)columns number:(int)number {
    
    BOOL found = NO;
    
    if (matrix.count > 0 && rows>0 && columns >0 ) {
        int row = 0;
        int column = columns-1;
        while (row < rows && column >= 0) {
            if ([matrix[row * columns + column] intValue] == number) {
                found = YES;
                break;
            }
            else if ([matrix[row * columns + column] intValue] > number) {
                --column;
            }
            else {
                ++row;
            }
        }
    }

    return found;
}

Swift

    func findNumber(_ matrix:[Int], _ rows:Int, _ columns:Int, _ number:Int) -> Bool {
        var found = false
        
        if matrix.count > 0 && rows > 0 && columns > 0 {
            var row = 0
            var 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 = column - 1
                } else {
                    row = row + 1
                }
            }
            
        }
        
        
        return found
    }

Python

def find_number(matrix ,rows,columns,number):
    found = False
    row = 0
    column = columns - 1
    while rows > 1 and columns > 1 :
        if matrix[row * columns + column] == number :
            found = True 
            break
        elif matrix[row * columns + column] > number :
            column = column -1
        else :
             row = row + 1

    return found


user_list = [1,2,8,9,2,4,9,12,4,7,10,13,6,8,11,15]
res = find_number(user_list,4,4,5)
print(res)

总结

1.考察的是对二维数组的理解及编程能力。二维数组在内存中占据连续的空间，在内存中从上到下存储各行元素，在同一行按照从左到右的顺序存储。因此我们可以根据行号和列号计算出相对于数组首地址的偏移量，从找到对应的元素。

2.考察分析问题的能力，当应聘者发现问题比较复杂时，能不能通过具体的例子找出其中的规律，能否解决这个问题的关键所在，这个题目只要从一个具体的二维数组的右上角开始分析，就能找到查找的规律，从而找到解决问题的突破口。