本文共 1968 字，大约阅读时间需要 6 分钟。

题目描述：

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

解题思路：

我们需要不断地缩小查找域，来判断整数的是否存在。而缩小查找域可以有两种思路：

一、每次取出二维数组的右上角（或者左下角），下面以右上角为例：

       如果右上角的数等于我们需要查找的数，返回True，整数存在在二维数组当中；

       如果查找域已经不存在数字了，那么返回False，整数不存在在二维数组当中；

       如果右上角的数大于查找的整数，那么去掉包含右上角的数的这一列（因为这一列其他所有的数按照题目要求都会大于整数），缩小了查找域，再继续返回查找

       如果右上角的数小于查找的整数，那么去掉包含右上角的数的这一行（因为这一行其他所有的数按照题目要求都会小于整数），缩小了查找域，再继续返回查找

同理，如果要用左下角做判断也是类似。

样例代码：

def reduceCols():    '''    use to reduce cols    '''    global cols    cols -= 1    judgeFunc(arrayOne)def reduceRows():    '''        use to reduce rows        '''    global reduce_rows    reduce_rows -= 1    judgeFunc(arrayOne)def judgeFunc(arrayOne):    '''    compare flag and the number at the top right of the array(call it x):         if    x is not exit    :   return False(flag is not in arrayOne)         elif  x ==  flag       :   return True(flag is in arrayOne)         elif  x >  flag        :   use the func to reduce cols,and return this judgeFunc         elif  x <  flag        :   use the func to reduce rows,and return this judgeFunc    :param reduce_rows:use to get the number of new array's rows    '''    global rows,reduce_rows,cols,cols    try:        x = arrayOne[rows - reduce_rows][cols - 1]    except:        print("flag does not exist")        return False    if x == flag:        print("flag exist")        return True    elif x > flag:        reduceCols()    elif x < flag:        reduceRows()if __name__ == '__main__':    x = input()    flag,arrayOne = x.split(',',1)    flag = int(flag)    arrayOne = eval(arrayOne)    rows = len(arrayOne)    reduce_rows = rows    cols = len(arrayOne[0])    judgeFunc(arrayOne)

二、（思考题）可以在第一步先用对角查询缩小查找域，继而再使用上述方法查找

       笔者在思考本题的时候在想，怎么可以更快的缩小查找域呢？

       想到每次取对角上面的数arrayOne[ i ][ i ]的值，将这个值与整数 flag 作比较，如果小于 flag 不就是直接去掉了一个正方形区域了吗？这样在当二维数组很大。而且查找的数比较靠后的时候相当有效，如果对角线走完了，再把剩下的区域的数组使用本方法或者上述的右上角缩小查询域方法都可以继续再查找。

至于代码嘛，笔者就没写了=_=，，，留给有兴趣的读者自己创造把~思路反正如上哦

嘿嘿，I am very glateful that 你看到这里了哦~下回再见ヾ(o◕∀◕)ﾉヾ

Thx

转载地址：http://ynggn.baihongyu.com/