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其实就是一个拆分开来的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
