·题目描述
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 输出：true
示例 2：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20 输出：false
·解题思路
想编写一个二维二分查找的算法，就是说将二维矩阵分为四个象限，根据中间值的大小判断要搜索的区域。但是每次对比完还需要查找余下三个象限的值，时间耗费比较多。
----如果想做该算法，需要搞清楚的事情是。当中间值 小于 target时候，需要查找的三个象限为左上、左下、右上；当中间值 大于 target 的时候，需要查找的三个象限为右上、左下、右下。
·Java代码
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
for(int i = 0; i < m ; i ++){
int[] temp = matrix[i];
if(find(temp, target, 0, n - 1)){
return true;
}
}
return false;
}
public static boolean find(int[] arr, int target, int lo, int hi ) {
if(lo > hi ) return false;
int mid = lo + (hi - lo ) / 2;
if(arr[mid] == target){return true;}
else if(arr[mid] > target){return find(arr, target, lo, mid - 1);}
else{return find(arr, target, mid + 1, hi);}
}
}------耗时太长了，还不如每一行使用二分查找。但是做一点点小小的优化，只有当每一行的第一个元素 小于 target ， 并且 最后一个元素 大于 target 的时候，才进行二分查找。
·Java 代码
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
for(int i = 0; i < m ; i ++){
int[] temp = matrix[i];
if(temp[0] <= target && temp[n - 1] >= target){
if(find(temp, target, 0, n - 1)){
return true;
}
}
}
return false;
}
public static boolean find(int[] arr, int target, int lo, int hi ) {
if(lo > hi ) return false;
int mid = lo + (hi - lo ) / 2;
if(arr[mid] == target){return true;}
else if(arr[mid] > target){return find(arr, target, lo, mid - 1);}
else{return find(arr, target, mid + 1, hi);}
}
}当然还有一个暴力遍历求解就不说了。
