原題

寫出一個(gè)高效的算法來搜索 m × n矩陣中的值。
這個(gè)矩陣具有以下特性：
每行中的整數(shù)從左到右是排序的。
每行的第一個(gè)數(shù)大于上一行的最后一個(gè)整數(shù)。

[
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

給出 target = 3，返回 true

解題思路

• 首先可以把這個(gè)二維數(shù)組看成一維數(shù)組，3 * 4 的矩陣可以看成一個(gè)12個(gè)數(shù)的一維數(shù)組，所以對(duì)于50的坐標(biāo)為(2,3)，可以看成第array[11]

[1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 50]

• 一維數(shù)組與二維數(shù)組的轉(zhuǎn)化

2 = 11 / 4, 3 = 11 % 4   # width = 4

完整代碼

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix:
            return False
        
        start = 0
        width = len(matrix[0])
        end = len(matrix) * width - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if matrix[mid / width][mid % width] == target:
                return True
            elif matrix[mid / width][mid % width] > target:
                end = mid
            else:
                start = mid
            
        if matrix[start / width][start % width] == target:
            return True
        if matrix[end / width][end % width] == target:
            return True
        return False