搜索2维数组；如果数组中存在目标值，返回true，否则返回false
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
For example,
Consider the following 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] ]
Given target = 5, return true.
Given target = 20, return false.
遍历的话肯定效率低下。设立游标移动搜索。那么问题是从哪里开始搜索？
比较好的办法是从右上角开始。如果右上角的数字大于target，那么这一列没有target；向左一列移动
如果小于target，那么这一行没有target，向下一行移动
搜索停止的条件就是越界
Java代码：
1 package com.rust.cal; 2 3 public class Searcha2DMatrixII { 4 5 public static boolean searchMatrix(int[][] matrix, int target) { 6 if (matrix.length == 0 || matrix[0].length == 0) { 7 return false; 8 } 9 int dy = matrix[0].length - 1; 10 int delta = matrix[0][dy]; 11 int dx = 0; 12 while(dx < matrix.length && dy >= 0){ 13 if (matrix[dx][dy] == target) { 14 return true; 15 } else if (matrix[dx][dy] < target) { 16 dx++; 17 } else { 18 dy--; 19 } 20 } 21 return false; 22 } 23 public static void main(String args[]){ 24 int matrix[][] = { 25 {1 ,2 ,3 ,4 ,9 }, 26 {6 ,7 ,8 ,10,19}, 27 {17,18,30,31,32} 28 }; 29 30 int matrix1[][] = { 31 {1,2}, 32 {4,5}, 33 {6,17}, 34 {10,20} 35 }; 36 37 int matrix2[][] = { 38 {1,3,5,7,9,13,17}, 39 {2,4,6,8,10,16,20} 40 }; 41 42 System.out.println("matrix has 17? " + searchMatrix(matrix, 17)); 43 System.out.println("matrix has 18? " + searchMatrix(matrix, 18)); 44 System.out.println("matrix has 19? " + searchMatrix(matrix, 19)); 45 System.out.println("matrix1 has 4? " + searchMatrix(matrix1, 4)); 46 System.out.println("matrix2 has 4? " + searchMatrix(matrix2, 4)); 47 48 } 49 }
输出：
matrix has 17? true matrix has 18? true matrix has 19? true matrix1 has 4? true matrix2 has 4? true
