solved 'Search a 2D Matrix II' on LeetCode https://leetcode.com/problems/search-a-2d-matrix-ii/

search_matrix_ii_binary_search.py

# Do binary search for each row. O(mlgn).
# Run time: 224 ms
class Solution:
    # @param {integer[][]} matrix
    # @param {integer} target
    # @return {boolean}
    def searchMatrix(self, matrix, target):
        m, n = len(matrix), len(matrix[0])
        # Edge case.
        if m == 0 or n == 0:
            return False
        # Eliminate impossible targets.
        if target < matrix[0][0] or target > matrix[-1][-1]:
            return False
        
        # Binary search on each row.
        for row in matrix:
            # Impossible to find target when the first
            # element it greater.
            if row[0] > target:
                break
            left, right = 0, n
            while left < right:
                middle = (left + right) / 2
                if row[middle] == target:
                    return True
                elif row[middle] < target:
                    left = middle + 1
                else:
                    right = middle
        
        return False

search_matrix_ii_upper_right.py

# Beautiful O(m+n) algorithm, from
# https://leetcode.com/discuss/48852/my-concise-o-m-n-java-solution
# Run time: 136 ms
class Solution:
    # @param {integer[][]} matrix
    # @param {integer} target
    # @return {boolean}
    def searchMatrix(self, matrix, target):
        m, n = len(matrix), len(matrix[0])
        # Edge cases.
        if m == 0 or n == 0:
            return False
        # Eliminate impossible targets.
        if target < matrix[0][0] or target > matrix[-1][-1]:
            return False
        
        # Start from upper-right corner; a zig-zag trail.
        row, col = 0, n - 1
        while col >= 0 and row < m:
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] > target:
                # Only consider left.
                col -= 1
            elif matrix[row][col] < target:
                # Only consider below.
                row += 1

        return False