LeetCode 74 LintCode 28 – Python 3 (Week 10 – 02)

 class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix: return False
         
        row, column = len(matrix), len(matrix[0])
        if not row or not column: return False 
        
        start, end = 0, row * column - 1
        
        while start + 1 < end:
            mid = int(start + (end - start) / 2)
            
            r = int(mid / column)
            c = mid % column
            
            if matrix[r][c] == target:
                return True
            elif matrix[r][c] < target:
                start = mid
            else:
                end = mid
        
        if matrix[int(start / column)][start % column] == target or matrix[int(end / column)][end % column] == target:
            return True
        return False

 class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix: return False
         
        row, column = len(matrix), len(matrix[0])
        if not row or not column: return False
        
        start, end = 0, row - 1
        
        while start + 1 < end:
            mid = int(start + (end - start) / 2)
            if matrix[mid][0] == target:
                return True
            elif matrix[mid][0] < target:
                start = mid
            else:
                end = mid
                
        if matrix[start][0] > target:
            r = start - 1
        elif start < end and matrix[end][0] <= target:
            r = end
        else:
            r = start
            
        if r < 0 or r >= row: return False
        
        start, end = 0, column - 1
        
        while start + 1 < end:
            mid = int(start + (end - start) / 2)
            
            if matrix[r][mid] == target:
                return True
            elif matrix[r][mid] < target:
                start = mid
            else:
                end = mid
                
        if matrix[r][start] == target or matrix[r][end] == target:
            return True
        return False