题目描述（中等难度）

74. Search a 2D Matrix - 图1

判断一个矩阵中是否存在某个数，矩阵是有序的。

解法一 二分法

看到了有序序列，啥都不用想直接二分，只需要考虑到怎么把二分时候的下标转换为矩阵的行、列下标就可以了，很简单，用除法和求余就够了。

  1. public boolean searchMatrix(int[][] matrix, int target) {
  2.     int rows = matrix.length;
  3.     if (rows == 0) {
  4.         return false;
  5.     }
  6.     int cols = matrix[0].length;
  7.     int left = 0;
  8.     int right = rows * cols - 1;
  9.     while (left <= right) {
  10.         int mid = (left + right) / 2;
  11.         int temp = matrix[mid / cols][mid % cols];
  12.         if (temp == target) {
  13.             return true;
  14.         } else if (temp < target) {
  15.             left = mid + 1;
  16.         } else {
  17.             right = mid - 1;
  18.         }
  19.     }
  20.     return false;
  21. }

时间复杂度：O ( log ( n ) )。

空间复杂度：O ( 1 )。

总

这道题的二分法，比较简单，大家可以看下33题，相信对二分法会有一个更深刻的理解。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情