题目内容

题目来源：剑指offer、LeetCode

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

题目思路

这个题目最直接的想法就是从左上角开始看，假设要查找的数是大于左上角的数字，那么要查找的数必然在该数字的右边或者下边。那么问题来了，右边或者下边就意味着右下角的矩形部分是重复的，这就给编程带来了难度。

因此经过仔细观察，发现本题可以用如下方式规避上述问题。从右上角或者左下角入手进行比较。以左下角为例，假如该数字大于左下角的数，那么左下角数所在的这一列都可以被排除了，假如该数字小于左下角的数，那么左下角的数所在的这一行就可以都被排除了。通过这样的方法，一次就可以排除一行或者一列，大大降低了难度。不会出现重叠的情况了。

这种题目就是比较巧妙，学习经验。

Python代码

# -*- coding:utf-8 -*-class Solution:    # array 二维列表    def Find(self, target, array):        # write code here        if not array or not target:            return        row=len(array)        col=len(array[0])        if row==1 and col==0:            return False        i=row-1        j=0        while j=0:            if target>array[i][j]:                j+=1            elif target