Leetcode: Search a 2D Matrix (12ms) Analysis and solution)

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.

Analysis:

It's an simple transformation of Binary search. Consider the 2D matrix as a line and use the BS directly. 

The key is how to transform the 2D index into a linear index, see the codes for detail. 

/////////////////////////////////////////////////////////

//code 12ms

class Solution {

public:

       bool searchMatrix(vector<vector<int>>& matrix, int target) {

              int n = matrix.size(), m = matrix[0].size();

              int l = 0, r = m*n - 1, mid = (l + r) / 2;

              while (l <= r){

                     if (target<matrix[mid/m][mid%m]){

                           r = mid - 1;

                           mid = (l + r) / 2;

                     }

                     else if (target>matrix[mid/m][mid%m]){

                           l = mid + 1;

                           mid = (l + r) / 2;

                     }

                     else return true;

              }

              return false;

       }

};