数组、二分搜索二维矩阵

1、题目描述

https://leetcode-cn.com/problems/search-a-2d-matrix/

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。

该矩阵具有如下特性：

每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数（变成了240题的特例）。

通用模板就看 LeetCode240：搜索二维矩阵II https://blog.csdn.net/IOT_victor/article/details/104642324

本题解法在240基础上加了优化

2、代码详解

法一：缩小领域法

因为每一行递增，每一列递增。所以我们可以从右上角往左下角找或者从左下角往右上角找。

每次比较可以排除一行或者一列，时间复杂度为O(m+n)

class Solution(object):
    def searchMatrix(self, matrix, target):
        # m * n
        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])
        # 左下角（必须这么设置！左下角：最后一行的最小值）从下向上
        row = m - 1
        col = 0
        while row >= 0 and col <= n-1:
            # 优化:当前行的最大值 < target
            if matrix[row][n-1] < target:
                return False
            if matrix[row][col] > target:
                row -= 1
            elif matrix[row][col] < target:
                col += 1
            else:
                return True
        return False

        # # 右上角（必须这么设置！右上角：第一行的最大值）从上向下
        # row = 0  # 行
        # col = n - 1  # 列
        # while row <= m-1 and col >= 0:
        #     # 优化:当前行的最小值 > target
        #     if matrix[row][0] > target:
        #         return False
        #     if matrix[row][col] > target:  # 在本行中
        #         col -= 1
        #     elif matrix[row][col] < target:  # 加行
        #         row += 1
        #     else:
        #         return True
        # return False

matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
s = Solution()
print(s.searchMatrix(matrix, target))

法二：标准的二分查找模板

将二维矩阵拖为一维矩阵，然后就是一个有序的一维数组了，利用二分查找就行

本文地址：https://blog.csdn.net/IOT_victor/article/details/107081728