### 题目1
写出一个高效的算法来搜索 m × n矩阵中的值。
这个矩阵具有以下特性：
每行中的整数从左到右是排序的。
每行的第一个数大于上一行的最后一个整数。
考虑下列矩阵：
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
给出 target = 3，返回 true
**规则**
输入：int[][] 和int target
输出：boolean
case:
```
数组为null
二维数组为[[]]
边界
```
**思路**
这道题还是比较简单的，假设是m×n,m行n列，可以现在最后一个元素上进行二分查找，找到刚好大于target的数，然后在该行进行查找，复杂度为O(logm*logn)
```
public class Solution {
/*
* @param matrix: matrix, a list of lists of integers
* @param target: An integer
* @return: a boolean, indicate whether matrix contains target
*/
public boolean searchMatrix(int matrxi[][],int target) {
// write your code here
int rowLen = matrxi.length;
if(rowLen == 0){
return false;
}
int colLen = matrxi[0].length;
if(colLen == 0){
return false;
}
int y = findY(matrxi,target,0,rowLen-1);
if(matrxi[y][colLen-1] == target) {
return true;
}
int x = findX(matrxi[y],target,0,colLen-1);
if(x >-1) {
return true;
}
return false;
}
/*第一个大于等于target的index*/
public int findY(int matrxi[][],int target,int min,int max) {
int rowLen = matrxi.length;
int colLen = matrxi[0].length;
int ret = rowLen-1;
while(true) {
if(min > max || min < 0 || max >colLen-1) {
return ret;
}
int mid = min + (max-min)/2;
if(matrxi[mid][colLen-1] == target) {
return mid;
}else if(matrxi[mid][colLen-1] < target) {
min = mid + 1;
}else if(matrxi[mid][colLen-1] > target) {
max = mid - 1;
ret = mid;
}
}
}
public int findX(int matrxi[],int target,int min,int max) {
int length = matrxi.length;
while(true) {
if(min > max || min < 0 || max > length-1) {
return -1;
}
int mid = min + (max-min)/2;
if(matrxi[mid] == target) {
return mid;
}else if(matrxi[mid] < target) {
min = mid + 1;
}else if(matrxi[mid] > target) {
max = mid - 1;
}
}
}
}
```
**谬误**
这个题目忘记考虑了边界条件，导致边界处理的不会。例如，查找每行最后一个元素时，没有考虑到不存在大于target的情况，还是要严格按照三个步骤：规则，思路，代码
### 题目2
在一个二维数组中，每一行都从左到右递增，每一列都从上到下递增，请完成一个函数，输入一个二维数组和一个整数，判断数组中是否含有改整数。
**规则**
输入：int[][] 和 int target
输出：int 出现次数
CASE：
```
数组为null
数组0行或0列
考虑边界条件
```
**思路**
从右上角的元素e出发，如果e大于target说明e所在的列都大于target，e移至左边一个元素；如果e小于target说明e所在的行都小于target，e向下走一步；一直走直到走到左下角。复杂度为O(m+n)
**代码**
```
public int findTarget(int matrxi[][],int target) {
if(matrxi == null) return false;
int rowLen = matrxi.length;
if(rowLen == 0)return false;
int colLen = matrxi[0].length;
if(colLen == 0)return false;
int row = 0;
int col = colLen - 1;
while(true) {
if(row == rowLen|| col == -1) {
return false;
}
int sel = matrxi[row][col];
if(sel == target) {
return true;
}else if(sel < target) {
row ++;
}else{ // sel > target
col --;
}
}
}
```
### 题目3
写出一个高效的算法来搜索m×n矩阵中的值，返回这个值出现的次数。
这个矩阵具有以下特性：
每行中的整数从左到右是排序的。
每一列的整数从上到下是排序的。
在每一行或每一列中没有重复的整数。
样例
考虑下列矩阵：
[
[1, 3, 5, 7],
[2, 4, 7, 8],
[3, 5, 9, 10]
]
给出target = 3，返回 2
**规则**
输入：int[][] 和 int target
输出：boolean
CASE：
```
数组为null
数组0行或0列
考虑边界条件
```
**思路**
与题目2一样，从右上角到左下角，一直查找即可
**代码**
```
public int findTarget(int matrix[][],int target) {
if(matrix == null) return 0;
int rowLen = matrix.length;
if(rowLen == 0)return 0;
int colLen = matrix[0].length;
if(colLen == 0)return 0;
int row = 0;
int col = colLen - 1;
int count = 0;
while(true) {
if(row == rowLen|| col == -1) {
return count;
}
int sel = matrix[row][col];
if(sel == target) {
count++;
row ++;
col --;
}else if(sel < target) {
row ++;
}else{ // sel > target
col --;
}
}
}
```
