p74

 
public class  {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length;
		if (n < 1)
			return false;
		int m = matrix[0].length;
		if (m < 1)
			return false;
		int left = 0;
		int right = n;
		while (left < right) {
			int mid = left + (right - left) / 2;
			if (matrix[mid][0] == target) {
				return true;
			}
			if (matrix[mid][0] < target) {
				left = mid + 1;
			} else {
				right = mid;
			}

		}
		for (int i = 0; i < left ; i++) {
			int l = 0;
			int r = m;
			while (l < r) {
				int mid = l + (r - l) / 2;
				if (matrix[i][mid] == target) {
					return true;
				}
				if (matrix[i][mid] < target) {
					l = mid + 1;
				} else {
					r = mid;
				}

			}
		}
		return false;
    }
}