#28 Search a 2D Matrix

题目描述：

Write an efficient algorithm that searches for a value in an mx 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. Have you met this question in a real interview?  Yes 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

题目思路：

这题也是搜两遍的思想：先根据matrix[row][0]找到target可能所在的row，然后在row中再用binary search找到target或者返回false。

Mycode（AC = 13ms）：

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) { // write your code here int num_rows = matrix.size(); if (num_rows == 0) return false; int num_cols = matrix[0].size(); // find the target row for searching target int upper = 0, down = num_rows - 1; while (upper < down) { int mid = (upper + down) / 2; if (matrix[mid][0] >= target) { down = mid - 1; } else { if (matrix[mid][num_cols - 1] < target) { upper = mid + 1; } else { upper = mid; break; } } } // find the target at the target row int left = 0, right = num_cols; while (left < right) { int mid = (left + right) / 2; if (matrix[upper][mid] == target) { return true; } else if (matrix[upper][mid] < target) { left = mid + 1; } else { right = mid - 1; } } return matrix[upper][left] == target; } };