# Binary Search on Matrix #### [74. Search a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/) To determine which row to search, you can check the last element of each row. This can be achieved by using binary search. Then binary search in that row to find the element. ```java public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return false; } int m = matrix.length, n = matrix[0].length; int row = findRow(matrix, target, 0, m - 1); int left = 0, right = n - 1; while (left + 1 < right) { int mid = left + (right - left) / 2; if (matrix[row][mid] == target) { return true; } else if (matrix[row][mid] < target) { left = mid; } else { right = mid; } } return matrix[row][left] == target || matrix[row][right] == target; } private int findRow(int[][] matrix, int target, int top, int bottom) { int last = matrix[0].length - 1; while (top + 1 < bottom) { int mid = top + (bottom - top) / 2; if (matrix[mid][last] >= target) { bottom = mid; } else { top = mid; } } if (target <= matrix[top][last]) { return top; } return bottom; } ``` #### [240. Search a 2D Matrix II](https://leetcode.com/problems/search-a-2d-matrix-ii/) 1\. BFS, starting from top left node, traverse to right and down direction on each node, until find the target. *T: O(m \*n) S: O(m\*n) TLE* ```java int[][] dirs = {{0,1}, {1,0}}; public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return false; } Queue queue = new LinkedList<>(); queue.offer(new int[]{0, 0}); while (!queue.isEmpty()) { int[] curt = queue.poll(); if (matrix[curt[0]][curt[1]] > target) continue; if (matrix[curt[0]][curt[1]] == target) { return true; } for (int[] dir : dirs) { int newx = dir[0] + curt[0]; int newy = dir[1] + curt[1]; if (newx < matrix.length && newy < matrix[0].length) { queue.offer(new int[]{newx, newy}); } } } return false; } ``` 2\. Divide and Conquer, Divide the matrix into 4 subregion: ``` zone 1 zone 2 * * * * | * * * * * * * * | * * * * * * * * | * * * * * * * * | * * * * ----------------------- * * * * | * * * * * * * * | * * * * * * * * | * * * * * * * * | * * * * zone 3 zone 4 ``` * matrix\[mid\_row]\[mid\_col] == target: return true * matrix\[mid\_row]\[mid\_col] > target: search in region 1,2,3 * matrix\[mid\_row]\[mid\_col] < target: search in region 2,3,4 *T: O((MN)log4(3)) because the recursive equation of this solution is T(n) = 3T(n/4) + O(1).* *It reduces the problem by 3/4 every function call. The base case would be a 1 x 1 matrix. So* *`mn * (3/4)^x = 1`,* *thus we have `x = log(3/4, 1/mn) = log(4/3, mn)`* $$a = b$$ *Thus,* *`T(m * n) = O(lg(mn)) = O(lg(m) + lg(n))`* ```java public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false; if(matrix.length == 1 && matrix[0].length == 1) return matrix[0][0] == target; return search(matrix, 0, matrix.length - 1, 0, matrix[0].length - 1, target); } private boolean search(int[][] matrix, int sRow, int eRow, int sCol, int eCol, int target) { if (sRow > eRow || sCol > eCol) return false; if (sRow == eRow && sCol == eCol) return matrix[sRow][sCol] == target; int mRow = (sRow + eRow) / 2; int mCol = (sCol + eCol) / 2; if (matrix[mRow][mCol] == target) { return true; } else if (matrix[mRow][mCol] > target) { // search 1,2,3 return search(matrix, sRow, mRow, sCol, mCol, target) || search(matrix, mRow + 1, eRow, sCol, mCol, target) || search(matrix, sRow, mRow, mCol + 1, eCol, target) ; } else { // search 2,3,4 return search(matrix, mRow + 1, eRow, mCol + 1, eCol, target) || search(matrix, mRow + 1, eRow, sCol, mCol, target) || search(matrix, sRow, mRow, mCol + 1, eCol, target) ; } } ``` 3\. Search Space Reduction Starts from top-right element, move down if `matrix[row][col] < target`, move left if `matrix[row][col] > target`. *T: O(m + n)* ```java public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return false; } int m = matrix.length, n = matrix[0].length; int row = 0, col = n - 1; while (row < m && col >= 0) { if (matrix[row][col] == target) return true; else if (matrix[row][col] > target) { col--; } else { row++; } } return false; } ``` #### [378. Kth Smallest Element in a Sorted Matrix](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/) Binary Search between the `max` and `min` elements in the matrix. The `min` is the top-left element, `max` is the bottom-right element. Each search, take the `mid` as a threshold, and count how many elements are smaller than the threshold. *T: O(N \* log(max - min)) S: O(1)* ```java public int kthSmallest(int[][] matrix, int k) { int m = matrix.length, n = matrix[0].length; int left = matrix[0][0], right = matrix[m - 1][n - 1]; while (left < right) { int mid = left + (right - left) / 2; if (hasSmaller(matrix, mid) < k) { left = mid + 1; } else { right = mid; } } return left; } private int hasSmaller(int[][] matrix, int x) { int count = 0; for (int[] row : matrix) { int n = matrix[0].length; if (row[n - 1] <= x) { count += row.length; } else { for (int i = 0; i < n && row[i] <= x; i++) { count++; } } } return count; } ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://howardyangemail.gitbook.io/decode-leetcode/binary-search/binary-search-on-matrix-1.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.