特定条件下的查找

问题描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
分析
思路1
查找的暴力思路，O(n^2)
思路2
根据题目所给数组的特殊性质，行与列的值是依次递增的，根据这个性质，从右上角或者左下角的值开始于关键值key进行比较，如果同key相等就返回True，代表找到了，如果大于key就将row的值加1，如果小于key就将column的值减去1。我刚演算了一下，考虑了复杂度为O(n)，我也不知道对不对，下面的算法是根据思路2来写的。
思路3
基于折半的思想，理论上可以达到O(lgn)。思路是取row和column的中间值，之后可以去掉3/n的元素，当然也要考虑矩阵是不是方阵，去掉之后会产生3个矩阵，之后再使用相同的方法去取那三个矩阵的中间值。依次类推，考虑了一下可以用递归写写试试，不过还是比较麻烦。
Python小记

1. 创建一个i行j列的数组，其实Python里不再叫数组了，而是列表。

   mylist = [([0] * j) for k in range(i)]

吐槽一下C创建i行j列数组为

mylist[i][j]

1. 取列表列数和行数

   rows = len([x[0] for x in mylist])
   columns = len(mylist[0])

Python实现

# coding:utf-8
# 特定条件下的查找

def find(matrix, key):
	if(len(matrix) == 0):
		return False
	rows = len([x[0] for x in matrix])
	columns = len(matrix[0])
	if(rows > 0 and columns > 0):
		row = 0
		column = columns - 1
		while(row < rows and column >= 0):
			if(matrix[row][column] == key):
				return True
			elif(matrix[row][column] > key):
				column -= 1
			else:
				row += 1
	return False

def test(name, matrix, key, expected):
	if(name != ""):
		print name + "  begins:"
	
	result = find(matrix, key)
	if(result == expected):
		print "pass"
	else:
		print "failed"

def test1():
	matrix = [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]]
	test("test1", matrix, 7, True)

def test2():
	matrix = [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]]
	test("test2", matrix, 5, False)

def test3():
	matrix = [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]]
	test("test3", matrix, 1, True)

def test4():
	matrix = [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]]
	test("test4", matrix, 15, True)

def test5():
	matrix = [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]]
	test("test5", matrix, 0, False)

def test6():
	matrix = [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]]
	test("test6", matrix, 16, False)

def test7():
	test("test7", [], 7, False)

test1()
test2()
test3()
test4()
test5()
test6()
test7()