# 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<int[]> 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$$&#x20;

*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.&#x20;

*T: O(N \* log(max - min))  S: O(1)*&#x20;

```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;
    }
```