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.
For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.
解法：
通過binary search啦悬而！曹体，首先這個matrix其實(shí)就是一個拆分開來的sortedlsit，我們先判斷是在那個row里面，在對row是用binary search 或者 x in ls的py 的語法
class Solution(object):
# def bs(self,ls,key):
# h = 0
# e = len(ls)-1
#
# while True:
# if h == e and ls[h] != key:
# return False
# m = h+e/2
# if ls[m] > key:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
for i in matrix:
h ,t = i[0],i[-1]
if h == key or t == key:
return True
if h<target and t> target:
return target in i
return False
def bs(self,ls,t):
s = 0
e = len(ls)-1
while True:
print(s,e)
if e-s == 1:
return ls[s] == t or ls[e] == t
m = int(((s+e)+0.0)/2)
if ls[m] == t:
return True
if ls[m] > t:
e = m
else:
s = m
return False
