leetcode: Search a 2D Matrix

Problem Description:

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 and Precautions:

(1) start from the top right conner (m-1, n-1) of the matrix, if the target is equal to it. then return true. if the target is less than it, then it has to be the in the row (m-1), don’t have to consider other rows. if the target is larger than it. then the target has to be in the smaller matrix with (m-2, n-1) as the top right conner. Repeat this process until the matrix become a 1 * 1, and determine if target is in it or not. The time complexity is O(m+n)

(2) just perform the binary search as in one dimensional array. Since 2-d array is actually a linear array in the memory, let the head index be 0 and the tail index be m * n -1, just perform a standard binary search over the interval [0, m*n-1] is ok. The time complexity is log(m*n) = log m + log n

(3) First use binary search to find the row where target could be in, and perform another binary search on that row to find the target exists or not. the time complexity would be the sum of these two binary search which is log m + log n

Written on May 16, 2013