Problem¶

You are given an m x n integer matrix matrix with the following two properties:

• Each row is sorted in non-decreasing order.
• The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Example 1:

**Input:** matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60|1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
**Output:** true

**Input:** matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60|1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
**Output:** false

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10**4 <= matrix[i][j], target <= 10**4

Solve¶

Binary searching¶

O(log n)

Takeaway¶

Just take the two dimension array as one dimension (Which c naively support with its stack base memory allocate).

• Allocating matrix[m][n] is equally allocating matrix[m*n]
• Which: matrix[x][y] = (int) *(matrix + x) +y) = (int) matrix[x*n+y]
• Still, the implementation in Leetcode using heap allocation

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
    int m = matrixSize;
    int n = *matrixColSize;
    for (int i = 0; i < n * m; i++){
        int* ptr = *(matrix + i/n) + i%n;
        if (i>0 && i%n==0) printf("\n");
        printf("%p ", ptr);
    }
    return false;
}

By checking with this code stdout give me this
[input]

[[1,3,5,7],[10,11,16,20],[23,30,34,60|1,3,5,7],[10,11,16,20],[23,30,34,60]]  
3

[stdout]

0x602000000030 0x602000000034 0x602000000038 0x60200000003c  
0x602000000050 0x602000000054 0x602000000058 0x60200000005c  
0x602000000070 0x602000000074 0x602000000078 0x60200000007c

Which mean, it not possible using the array directly by pointer or (int) *(matrix + x) +y) != (int) *matrix + x*n +y

Actual implementation¶

O(log n)

I like to use binary search that the start of left, right is not in the array, example:

• An array matrix that span over [0..=n] range (inclusive), left, right = -1, n+1
• So when calculating mid=(left+right)//2, we can landing mid in any number in [-1..=n+1] range. Giving me a easier way to controlling where left and right end up.
• The search function always end with left == mid == right -1.

While this isn’t necessary in this exact problem, but here I trying land matrix[left] <= target < matrix[right] (and by the break stop definition, we also have left = right -1 = mid = (left + right) // 2). So:

• If matrix[left] != matrix[target], there isn’t any thing in the matrix equal to target (as there isn’t any element between maxtrix[left..right] ), return False
• If matrix[left] == matrix[target], we found target, return True
  

  class Solution:
      def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
          m = len(matrix)
          n = len(matrix[0])
          l = -1
          r = m*n
          for _ in range(trunc(log(n*m, 2)) +1):
              mid = (l + r) // 2
              if mid == l:
                  break
              if matrix[mid//n][mid%n] <= target:
                  l = mid
              else:
                  r = mid
  
          if matrix[l//n][l%n] == target:
              return True
          return False