https://leetcode.com/problems/search-a-2d-matrix/description/
使用 summary 里总结的 Binary Search 通用实现。两次 binary search：
- Left Column，寻找比 target 小的最大值rowIndex
- 在rowIndex所指row里，进行二分查找。
代码：
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
return false;
}
int rows = matrix.length;
int cols = matrix[0].length;
// not necessary. included in the logic below
// if (matrix[0][0] > target || matrix[rows - 1][cols - 1] < target) {
// return false;
// }
int start = 0;
int end = rows - 1;
int mid, rowIndex;
while (start <= end) {
mid = start + (end - start) / 2;
if (matrix[mid][0] == target) {
return true;
} else if(matrix[mid][0] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
if (end == -1) {
return false;
}
rowIndex = end;
start = 0;
end = cols - 1;
while(start <= end) {
mid = start + (end - start) / 2;
if (matrix[rowIndex][mid] == target) {
return true;
} else if (matrix[rowIndex][mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return false;
}
另一种思路是将该 matrix 理解为长度为 m*n 的 array，进行二分。index 需要转成 rowIndex，colIndex，来比较 item 与 target。
rowIndex = index / colsNum;
colIndex = index % colsNum;
