Search a 2D Matrix

Search a 2D Matrix

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.

For example,

Consider the following matrix:

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

Given target = 3, return true.

Key: Binary search (There may be better code than mine in locating row number. The edge condition is when only two rows left. Incorrect treatment may lead to incorrect answer or infinite loop.)

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        
        //locate row
        int rs = 0;
        int re = matrix.length - 1;
        while (re - rs > 1) {
            int rm = (rs + re) / 2;
            if (matrix[rm][0] > target) {
                re = rm;
            }
            else if (matrix[rm][0] < target) {
                rs = rm;
            }
            else {
                return true;
            }
        }
        
        int row = 0;
        
        if (matrix[rs][0] > target) {
            return false;
        }
        
        if (matrix[re][0] <= target) {
            row = re;
        }
        else {
            row = rs;
        }
        
        int start = 0;
        int end = matrix[row].length - 1;
        
        if (matrix[row][start] == target || matrix[row][end] == target) {
            return true;
        }
        else if (matrix[row][end] < target) {
            return false;
        }
        else {
            //might be in this row
            while (start < end) {
                if (matrix[row][start] == target || matrix[row][end] == target) {
                    return true;
                }
                int mid = (start + end) / 2;
                if (matrix[row][mid] > target) {
                    end = mid - 1;
                }
                else if (matrix[row][mid] < target) {
                    start = mid + 1;
                }
                else {
                    return true;
                }
            }
            return false;
        }
    }
}