题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请实现一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
分析:二分法。给定数组array(行数:rows,列数:lows,待查找元素:data),首先,遍历数组右上角的元素(i = 0, j = cols -1)如果arr[i, j] == data,则直接返回True;如果arr[i][j] > data,则说明这一列其它的数字也一定大于data,因此没有必要继续查找了。对行同理。
code:
def findWithBinary(arr, data):
if arr is None:
return
i = 0
rows = len(arr)
cols = len(arr[0])
i = 0
j = cols - 1
while i < rows and j >= 0:
# 在数组中找到data,返回
if arr[i][j] == data:
return True
# 当前遍历到数组中的值大于data,data肯定不在这一列中
elif arr[i][j] > data:
j -= 1
# 当前遍历到数组中的值小于data,data肯定不在这一行中
else:
i += 1
return False
if __name__ == "__main__":
arr = [[0, 1, 2, 3, 4], [10, 11, 12, 13, 14], [20, 21, 22, 23, 24], [30, 31, 32, 33, 34], [40, 41, 42, 43, 44]]
print(findWithBinary(arr, 17))