Python算法——如何在有规律的二维数组中进行高效数据查找_python二维数组中找数

要求：

       二维数组每一行按照从左到右递增顺序排列，每一列按照从上到下顺序排列。实现一个函数，输入一个整数判断数组中是否含有该整数。

分析：

       最简单的方法就是对二维数组进行顺序遍历，然后判断待查找元素是否在数组中，这种时间复杂度为O(M*N)，M，N分别为二维数组行数和列数。

但顺序遍历不是最好的方法，当数组有序的时候，二分查找是一个很好的方法，具体思路如下：给定数组array(行数：rows，列数：columns，待查找元素：data)，首先遍历数组右上角元素(i=0,j=columns-1)，如果array[i][j]==data，则在二维数组中找到了data，直接返回；如果array[i][j]>data，则说明这一列其他元素也一定大于data，因此，通过 j- 操作排除这一列。同理，如果array[i][j]<data，则说明这一行中其他数字一定比data小，因此，通过 i+ 操作排除这一行。依次类推，直到遍历完数组结束。

代码实现：

# -*- coding:utf-8 -*-
def findWithBinary(array,data):
    if array == None:
        return False
    #从二维数组右上角元素开始遍历
    i = 0
    rows = len(array)
    columns = len(array[0])
    j = column