搜索二维矩阵II
问题描述：
编写一个高效的算法来搜索
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解题思路：
采用二分查找！！！
- 矩阵不存在，返回false
- 某一行的第一个元素大于了
target，当前行和后边的所有行都不用考虑了，直接返回false- 某一行的最后一个元素小于了
target，当前行就不用考虑了，换下一行
//提交版class Solution {public boolean searchMatrix(int[][] matrix, int target){if(matrix.length==0 || matrix[0].length == 0)return false;for (int i =0;i<matrix.length;i++){if (matrix[i][0] > target)return false;if ((matrix[i][matrix[i].length - 1]) < target)continue;int col = binarySearch(matrix[i], target);if (col != -1)return true;}return false;}public int binarySearch(int[] nums, int target){int low = 0;int high = nums.length-1;while (low <= high){int mid = (high - low)/2 + low;int num = nums[mid];if (num == target)return mid;else if (num > target) {high = mid - 1;}else {low = mid + 1;}}return -1;}
}//带有输入输出版
import java.util.Arrays;public class hot18_searchMatrix {public boolean searchMatrix(int[][] matrix, int target){if(matrix.length==0 || matrix[0].length == 0)return false;for (int i =0;i<matrix.length;i++){if (matrix[i][0] > target)return false;if ((matrix[i][matrix[i].length - 1]) < target)continue;int col = binarySearch(matrix[i], target);if (col != -1)return true;}return false;}public int binarySearch(int[] nums, int target){int low = 0;int high = nums.length-1;while (low <= high){int mid = (high - low)/2 + low;int num = nums[mid];if (num == target)return mid;else if (num > target) {high = mid - 1;}else {low = mid + 1;}}return -1;}public static void main(String[] args){int[][] 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}};int target = 5;System.out.println("输入：" + Arrays.deepToString(matrix));hot18_searchMatrix hot18SearchMatrix = new hot18_searchMatrix();boolean result = hot18SearchMatrix.searchMatrix(matrix,target);System.out.println("输出：" + result);}}
