Search a 2D Matrix I,II

I

• 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.

Complexity log(m) + log(n)

First search the first column to decide which row using binary search

Then, search the row from step one using binary search

class Solution:

    def searchMatrix(self, matrix, target):

        row = len(matrix)

        if row ==0:

            return False

        col = len(matrix[0])

        start,end = 0,row-1

        while start <end:

            mid = (start+end)/2

            if matrix[mid][0] > target:

                end = mid-1

            elif matrix[mid][0] < target:

                start = mid+1

            else:

                return True

        row = end if target>=matrix[end][0] else end-1

        start,end = 0,col-1

        while start <=end:

            mid = (start+end)/2

            if matrix[row][mid] < target:

                start = mid+1

            elif matrix[row][mid] > target:

                end = mid-1

            else:

                return True

        return False

II

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

I used the solution from 1st problem, first narrow down the row,col only search rows where first element matrix[row][0] is not greater than target and column matrix[0][col] <= target, thus we get a smaller matrix, then use binary search, but this proven to ben slow

I saw solution in discuss, start from top right most element, if it's greater than target then row+=1, since it's can't be in the current row, else if it's less than target col-=1, since target is smaller than the smallest element in the column

https://leetcode.com/discuss/48852/my-concise-o-m-n-java-solution  

class Solution:

# @param {integer[][]} matrix

# @param {integer} target

# @return {boolean}

def searchMatrix(self, matrix, target):

row = len(matrix)

if row == 0:

return False

col = len(matrix[0])

i,j = 0,col-1

while i < row and j >=0:

value = matrix[i][j]

if value < target:

i+=1

elif value > target:

j-=1

else:

return True 

return False