Introduction

In computational problem-solving, efficiently finding a number in a sorted matrix is a classic problem. The goal is to discover a particular number in an `n x m` matrix where both rows and columns are sorted in increasing order. The challenge heightens when aiming to execute the search in O(log n) time complexity. This exploration will present efficient methods, detailed explanations, and a bold yet optimal approach for solving this problem.

Problem Definition

Given a 2D matrix of size `n x m`: • Each row is sorted in a non-decreasing order. • Each column is sorted in a non-decreasing order.

The task is to determine whether a given number exists in this matrix. The required time complexity is O(log n).

Suboptimal Approaches

An elementary approach could be using a brute force search which will run with a time complexity of O(n*m). Another more refined approach employs the binary search method row-by-row or column-by-column, operating in O(n log m) time. While these methods improve efficiency, they fail to achieve the desired logarithmic complexity relative to `n`.

Optimal Approach with Binary Search

The approach to achieve O(log n) complexity employs Binary Search on a matrix treated as a singular sorted list. Follow these steps to adhere to this methodology:

1. Matrix Representation as a Single Sorted List
   Conceptually, view the 2D matrix as a single sorted array. This can be done by transforming the indices: • Total number of elements = `n * m`. • The middle element index in this virtual array can be computed. • The conversion from 1D index `k` to 2D matrix indices `(i, j)` is given by:

$$i = \frac{k}{m}$$

$$j = k \mod m$$

1. Binary Search Implementation
   Implement Binary Search as follows: • Initialize `low = 0` and `high = n * m - 1`. • Compute the middle element `mid = (low + high) / 2`. • Convert `mid` to matrix indices `(i, j)`. • Compare the matrix element `matrix[i][j]` with the target. • If found, return true. • If the element is larger than the target, reduce the high bound to `mid - 1`, else increase the low bound to `mid + 1`. • Repeat until `low` exceeds `high`.
2. Edge Cases
   Ensure the algorithm handles the following: • Identify when bounds overlap and define termination. • Decide the return value if the target does not exist (commonly `false`).

Complexity Analysis

• Time Complexity: $O(\log (n \times m)) = O(\log n + \log m)$ which reduces to $O(\log \min(n, m))$ when `n` and `m` are related. • Space Complexity: Since no additional data structures are needed beyond variable allocations, the space complexity is $O(1)$.

Example

Consider the matrix:

1 3 5 7 9 11