力扣74——搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

示例 1:

输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
输出: true

示例 2:

输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
输出: false

原题url：https://leetcode-cn.com/problems/search-a-2d-matrix/

既然是已经排好序的，那么我第一想到的就是二分查找了。每次进行对半查找，时间复杂度O(log(mn))，应该还是很高效。

我准备将查找分成两部分，第一是二分查找找到 target 在哪一行，然后从那一行再利用二分查找找到 target 在这一行的哪个位置。

让我们来看看代码：

class Solution {

    // 总行数
    int row;
    // 总列数
    int col;

    public boolean searchMatrix(int[][] matrix, int target) {
 if (matrix.length == 0 || matrix[0].length == 0) {
     return false;
 }

 row = matrix.length;
 col = matrix[0].length;
 // 利用二分法查询
 return binarySearchMatrix(matrix, 0, matrix.length - 1, target);
    }
		
		
    public boolean binarySearchMatrix(int[][] matrix, int left, int right, int target) {
 if (left > right) {
     return false;
 }
 if (left == right) {
     int[] array = matrix[left];
     if (target < array[0] || target > array[col - 1]) {
  return false;
     }
						
						// 从数据中心查找
     return binarySearchArray(array, 0, col - 1, target);
 }

 int middle = (left + right) / 2;
 int[] middleArray = matrix[middle];
 if (middleArray[0] > target) {
     return binarySearchMatrix(matrix, left, middle - 1, target);
 } else if (middleArray[col - 1] < target) {
     return binarySearchMatrix(matrix, middle + 1, right, target);
 } else {
     return binarySearchArray(middleArray, 0, col - 1, target);
 }
    }
		
		
    public boolean binarySearchArray(int[] array, int left, int right, int target) {
 if (left > right) {
     return false;
 }
 if (left == right) {
     return array[left] == target;
 }

 int middle = (left + right) / 2;
 if (array[middle] > target) {
     return binarySearchArray(array, left, middle - 1, target);
 } else if (array[middle] == target) {
     return true;
 } else {
     return binarySearchArray(array, middle + 1, right, target);
 }
    }
}

class Solution {

    public boolean searchMatrix(int[][] matrix, int target) {
 if (matrix.length == 0 || matrix[0].length == 0) {
     return false;
 }

 int col = matrix[0].length;
 // 将二维数组拉成一维数组，利用二分法解决
 int left = 0;
 int right = matrix.length * col - 1;
 while (left <= right) {
     // 计算中间数的下标和值
     int middleIndex = (left + right) / 2;
     int middleval = matrix[middleIndex / col][middleIndex % col];
     if (middleval == target) {
  return true;
     }

     if (middleval < target) {
  left = middleIndex + 1;
     } else {
  right = middleIndex - 1;
     }
 }

 return false;
    }
}