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.

 

解题思路：

在有序队列中寻找目标值，典型的二分搜索应用。

可以有两种思路：（1）使用两次二分搜索，先二分搜索列，确定列之后再二分搜索行；（2）将所有元素看成一列有序数列，每个元素的下标是 row*n + col，这样只需使用一次二分搜索；

虽然第二种思路只使用一次二分搜索，代码简介，但是使用第一种思路更好：

1、方法2需要过多的“/”和“%”运算，大大降低了性能；

2、方法2对比方法1，时间复杂度没有提高；

3、由于所有元素标注为0~m*n，相比方法1先在n中二分搜索，再在m中二分搜索，方法2的做法更可能导致整数越界；

因此，选择使用方法1.

代码：

1 class Solution { 2 public: 3     bool searchMatrix(vector
     
      
       >& matrix, int target) { 4         int first = 0; 5         int last = matrix.size() - 1; 6         while (first < last) { 7             int mid = (first + last) / 2 + 1; 8             if (matrix[mid][0] > target) 9                 last = mid - 1;10             else 11                 first = mid;12         }13         14         if (matrix[first][0] > target)15             return false;16         17         int row = first;18         first = 0;19         last = matrix[row].size() - 1;20         while (first < last) {21             int mid = (first + last) / 2;22             if (matrix[row][mid] > target)23                 last = mid;24             else if (matrix[row][mid] == target)25                 return true;26             else 27                 first = mid + 1;28         }29         30         return (matrix[row][first] == target);31     }32 };