力扣 搜索二维矩阵

二分查找，闭区间与开区间的不同解法。

题目

乍一看，不是遍历一下找到元素就可以了。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {for (int[] ints : matrix) {for (int ans : ints) {if (ans == target) return true;}}return false;}
}

可以通过的，但还是可以优化一下的。这题可以用二分的思路，可以把整个矩阵看成一大个数组，若将矩阵每一行拼接在上一行的末尾，则会得到一个升序数组，我们可以在该数组上二分找到目标元素。但是这种方法在每一行元素个数不一时会失效。

时间复杂度：O(logmn)，空间复杂度：O(1)。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int low = 0, high = m * n - 1;while (low <= high) {int mid = (high - low) / 2 + low;int x = matrix[mid / n][mid % n];if (x < target) {low = mid + 1;} else if (x > target) {high = mid - 1;} else {return true;}}return false;}
}

以上为标准二分查找的写法，其中首尾做为边界，条件时while (low <= high)，接着如果目标值偏大则在右边找，即low = mid + 1，反之，目标值偏小时往左边找，即 high = mid - 1，然后当low指针从左边到target时扫了一遍，当high指针从右边到target时扫了一遍，当两个指针重叠相遇时，进一步判断两个指针定住的数是不是目标数，然后退出循环。

这题还可以先对行二分，再对列二分，进行两次二分查找。每行的第一个元素大于前一行的第一个元素，矩阵第一列的元素是升序的。对矩阵的第一列的元素二分查找，找到最后一个不大于目标值的元素，然后在该元素所在行中二分查找目标值是否存在。

时间复杂度：O(logmn)，空间复杂度：O(1)。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int rowIndex = binarySearchFirstColumn(matrix, target);if (rowIndex < 0) {return false;}return binarySearchRow(matrix[rowIndex], target);}public int binarySearchFirstColumn(int[][] matrix, int target) {int low = -1, high = matrix.length - 1;while (low < high) {int mid = (high - low + 1) / 2 + low;if (matrix[mid][0] <= target) {low = mid;} else {high = mid - 1;}}return low;}public boolean binarySearchRow(int[] row, int target) {int low = 0, high = row.length - 1;while (low <= high) {int mid = (high - low) / 2 + low;if (row[mid] == target) {return true;} else if (row[mid] > target) {high = mid - 1;} else {low = mid + 1;}}return false;}
}

其中，用了一个左开右闭区间的二分查找，可以先进行扩充边界，然后条件改为while (low < high)，接着low要设置为mid，退出的条件即当low跟high重叠时，此时的low是mid了，看是不是要找的target。当然，这题用左闭右开区间的二分查找也是类似，不过要注意以下返回值，要取到不大于目标值的最大行索引。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int rowIndex = binarySearchFirstColumn(matrix, target);if (rowIndex < 0) {return false;}return binarySearchRow(matrix[rowIndex], target);}
public int binarySearchFirstColumn(int[][] matrix, int target) {int low = 0, high = matrix.length;  while (low < high) {  int mid = (high - low) / 2 + low;  if (matrix[mid][0] <= target) {  low = mid + 1;} else {  high = mid;  }}return high-1; 
}public boolean binarySearchRow(int[] row, int target) {int low = 0, high = row.length - 1;while (low <= high) {int mid = (high - low) / 2 + low;if (row[mid] == target) {return true;} else if (row[mid] > target) {high = mid - 1;} else {low = mid + 1;}}return false;}
}

然后，也可以用最经典的标准二分模板去写。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int rowIndex = binarySearchFirstColumn(matrix, target);if (rowIndex < 0) {return false;}return binarySearchRow(matrix[rowIndex], target);}
public int binarySearchFirstColumn(int[][] matrix, int target) {// 初始化low为0，high为矩阵最后一行的索引int low = 0, high = matrix.length - 1;while (low <= high) {  // 当low不大于high时继续循环int mid = (high - low) / 2 + low;  // 计算中间位置// 如果中间位置的行的第一个元素小于或等于目标值，则该行及之后的行可能是候选行if (matrix[mid][0] <= target) {low = mid + 1;  } else {high = mid - 1; }}// 返回不大于目标值的最大行索引return high;  // 这里返回high，因为high指向的是不大于目标值的最大行索引或未找到返回-1}public boolean binarySearchRow(int[] row, int target) {int low = 0, high = row.length - 1;while (low <= high) {int mid = (high - low) / 2 + low;if (row[mid] == target) {return true;} else if (row[mid] > target) {high = mid - 1;} else {low = mid + 1;}}return false;}
}

二分查找模板巧记，先写好数组中的左右边界值，然后while (low <= high)，接着写mid的求值 int mid = (high - low) / 2 + low，再到判断，若目标值偏大往大的找即low指针右移，若目标值偏小往小的找即high指针左移，最后当low跟high重叠时对当前元素做判断，返回值依题而定。