28 · Search a 2D Matrix - LintCode

# Description

Write an efficient algorithm that searches for a target 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.
n × m < 50000

# Solution

2d matrix -> 1d array:

	int x = index / matrix[0].length;
	int y = index % matrix[0].length;

	public class Solution {
	/**
	* @param matrix: matrix, a list of lists of integers
	* @param target: An integer
	* @return: a boolean, indicate whether matrix contains target
	*/
	public boolean searchMatrix(int[][] matrix, int target) {
	if (matrix.length == 0 \|\| matrix == null \|\| matrix[0].length == 0 \|\| matrix[0] == null){
	return false;
	}

	int rows = matrix.length;
	int cols = matrix[0].length;

	int start = 0, end = rows * cols - 1;
	while (start + 1 < end) {
	int mid = start + (end - start) / 2;
	if (getIndex(matrix, mid) == target) {
	return true;
	}
	if (getIndex(matrix, mid) < target) {
	start = mid;
	} else {
	end = mid;
	}
	}

	if (getIndex(matrix, start) == target) {
	return true;
	}
	if (getIndex(matrix, end) == target) {
	return true;
	}

	return false;
	}

	private int getIndex(int[][] matrix, int index) {
	int x = index / matrix[0].length;
	int y = index % matrix[0].length;
	return matrix[x][y];
	}
	}

O (logm+logn)=O (logmn) ; m 和 n 分別是 row & col

O(1)