LeetCode Q74: 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.

Solution 1:
Binary search, but at the end, you need to search two rows before making a decision. Time complexity O(logm + logn).

	class Solution {
	public:
	bool searchMatrix(vector<vector<int>>& matrix, int target) {
	int l=0, h=matrix.size()-1;
	int rows=matrix.size();
	int cols=matrix[0].size();
	int targetRow=-1;
	while(l<=h){
	int m=(l+h)/2;
	if(target==matrix[m][0])
	return true;
	if(target>matrix[m][0]&&target>matrix[m][cols-1])
	l=m+1;
	if(target>matrix[m][0]&&target<=matrix[m][cols-1]){
	targetRow=m;
	break;
	}
	if(target<matrix[m][0])
	h=m-1;
	}
	if(targetRow==-1)
	return false;
	l=0;
	h=cols-1;
	while(l<=h){
	int m = (l+h)/2;
	if(target == matrix[targetRow][m])
	return true;
	if(target > matrix[targetRow][m])
	l = m+1;
	if(target < matrix[targetRow][m])
	h = m-1;
	}
	return false;
	}
	};

view raw gistfile1.txt hosted with ❤ by GitHub

Solution 2:
Start from up right corner, if larger than move down, if smaller than move left. Time complexity O(m+n)

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

view raw Q74-2.cpp hosted with ❤ by GitHub