Leetcode - 74. Search a 2D Matri

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.

Search a 2D Matrix

解法：
通过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