Write an efficient algorithm that searches for a value in an_m_x_n_matrix.

This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Have you met this question in a real interview?

Yes

Example

Consider the following matrix:

[
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
]

Giventarget = 3, returntrue.

1. two binary search search vertical to decide which row the element might be in

 public boolean searchMatrix(int[][] matrix, int target) {
        // write your code here
        if (matrix == null || matrix.length == 0 || matrix[0] == null ||  matrix[0].length == 0) {
            return false;
        }

        int start = 0;
        int end = matrix.length - 1;

        int x = 0;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (matrix[mid][0] > target) {
                end = mid;
            } else if (matrix[mid][0] == target) {
                return true;
            } else {
                start = mid;
            }
        }    
        if (matrix[start][0] >  target) {
            return false;
        } else if (matrix[start][0] == target || matrix[end][0] == target) {
            return true;
        }

        if (matrix[end][0] < target) {
            x = end;
        } else {
            x = start;
        }


        start = 0;
        end = matrix[0].length - 1;

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (matrix[x][mid] > target) {
                end = mid;
            } else if (matrix[x][mid] == target) {
                return true;
            } else {
                start = mid;
            }
        }

        if (matrix[x][start] == target || matrix[x][end] == target) {
            return true;
        }

        return false;



    }

1. treat the whole matrix as one single array, use /rowSize to get the rowIndex and %/rowSize to get the columnIndex

public boolean searchMatrix(int[][] matrix, int target) {
        // write your code here
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return false;
        }

        int start = 0;
        int x = matrix[0].length;
        int y = matrix.length;

        int end = x * y - 1;

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            int row = mid / x;
            int column = mid % x;

            if (matrix[row][column] == target) {
                return true;
            } else if (matrix[row][column] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (matrix[start / x][start % x] == target || matrix[end / x][end % x] == target) {
            return true;
        }

        return false;



    }