Matrix Binary Search

在matrix上做搜索，看一看要不要把二维坐标转成一维坐标。

• 二维(i, j)转一维：index = i * n + j, n = number of columns of the matrix
• 一维(index)转二维: i = index / n, j = index % n.

Search a 2D Matrix

这题就是比较典型的二维坐标转成一维来做的题

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return false;
        }

        int m = matrix.length, n = matrix[0].length;
        int start = 0, end = m * n - 1;

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            int i = mid / n, j = mid % n;
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        int i1 = start / n, j1 = start % n, i2 = end / n, j2 = end % n;
        if (matrix[i1][j1] == target || matrix[i2][j2] == target) {
            return true;
        }
        return false;
    }
}

Search a 2D Matrix II

这题用双指针来做， 指针起始位置在matrix的左下角。如果target < current, 移动横向的指针向右；如果target > current，移动竖向指针向上。

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return false;
        }

        int m = matrix.length, n = matrix[0].length;

        int i = m - 1, j = 0;
        while (i >= 0 && j < n) {
            int current = matrix[i][j];
            if (current == target) {
                return true;
            } else if (current < target) {
                j++;
            } else {
                i--;
            }
        }
        return false;
    }
}