for (int i = 0; i < row; i++) { if (target >= matrix[i][0] && target <= matrix[i][col - 1]) { for (int j = 0; j < col; j++) { if (matrix[i][j] == target) { returntrue; } } } }
returnfalse; }
Analysis
Time Complexity: O(m×n)
Space Complexity: O(1)
Find Row First, then Column Binary Search
We can scanning the rows of the matrix, If the target is larger than the last element of this row, the target must not be in this row, but only in the lower row of the matrix.
If we find the row which the target may appears, search this row.
for (int i = 0; i < row; i++) { if (target >= matrix[i][0] && target <= matrix[i][col - 1]) { if (binarySearch(matrix[i], target) != -1) { returntrue; } } }
returnfalse; }
publicstaticintbinarySearch(int[] arr, int target){ int start = 0; int end = arr.length - 1; while (start <= end) { int mid = start + (end - start) / 2; if (arr[mid] > target) { end = mid - 1; } elseif (arr[mid] < target) { start = mid + 1; } else { return mid; } }
return -1; }
Analysis
Time Complexity: O(m+logn)
Space Complexity: O(n)
2 Binary Search: Row and Column
Using the binary search on the elements of the first column of the matrix, find the last element that is not larger than the target, the target may be located in the row.
int rowIdx = binarySearchColumn(matrix, target); return binarySearchRow(matrix[rowIdx], target); }
publicstaticintbinarySearchColumn(int[][] arr, int target){ int left = 0; int right = arr.length - 1; while (left < right) { int mid = left + (right - left + 1) / 2; if (arr[mid][0] <= target) { left = mid; } else { right = mid - 1; } }
return left; }
publicstaticbooleanbinarySearchRow(int[] arr, int target){ int left = 0; int right = arr.length - 1; while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] > target) { right = mid - 1; } elseif (arr[mid] < target) { left = mid + 1; } else { returntrue; } }
return arr[left] == target; }
Analysis
Time Complexity: O(logm+logn)
Space Complexity: O(1)
One Binary Search
Merge the current row to the end of the previous row, we can get an ascending array, then we just use binary search algorithm to find the target.
// 1 Binary Search: from top left to bottom right publicstaticbooleansearchMatrix_one_bs(int[][] matrix, int target){ int row = matrix.length; int col = matrix[0].length;