### 題目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 --;
}
}
}
```
