Search in a Row-wise and Column-wise Sorted Matrix

Medium

Problem Statement

Given an `m x n` matrix where each row is sorted in ascending order and each column is also sorted in ascending order, write an efficient algorithm to search for a target value.

Examples

1Example 1

Input:

{
  "matrix": [
    [
      1,
      4,
      7,
      11,
      15
    ],
    [
      2,
      5,
      8,
      12,
      19
    ],
    [
      3,
      6,
      9,
      16,
      22
    ],
    [
      10,
      13,
      14,
      17,
      24
    ],
    [
      18,
      21,
      23,
      26,
      30
    ]
  ],
  "target": 5
}

Output:

true

2Example 2

Input:

{
  "matrix": [
    [
      1,
      4,
      7,
      11,
      15
    ],
    [
      2,
      5,
      8,
      12,
      19
    ],
    [
      3,
      6,
      9,
      16,
      22
    ],
    [
      10,
      13,
      14,
      17,
      24
    ],
    [
      18,
      21,
      23,
      26,
      30
    ]
  ],
  "target": 20
}

Output:

false

3Example 3

Input:

{
  "matrix": [
    [
      -5
    ]
  ],
  "target": -5
}

Output:

true