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.
Example
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.
Challenge
O(log(n) + log(m)) time
class Solution { public: /** * @param matrix, a list of lists of integers * @param target, an integer * @return a boolean, indicate whether matrix contains target */ bool searchMatrix(vector<vector<int> > &matrix, int target) { int m = matrix.size(); if (m == 0) return false; int n = matrix[0].size(); if (n==0) return false; int i = 0, j = m-1; while(i < j) { int k = (i + j + 1)/2; if (matrix[k][0] == target) return true; if(matrix[k][0] > target) j = k - 1; else i = k; } if (matrix[i][n-1] < target) return false; int row = i; i = 0, j = n-1; while(i <= j) { int m = (i+j)/2; if (matrix[row][m] == target) return true; if (matrix[row][m] > target) j = m-1; else i = m+1; } return false; } };
No comments:
Post a Comment