Search a 2D Matrix - Java Solution

1. Introduction

In this blog post, we'll explore a problem that combines elements of binary search and matrix manipulation. The challenge is to search for a target value in a 2D matrix, where each row is sorted, and each row starts with an element greater than the last element of the previous row. Our goal is to achieve this with an efficient O(log(m * n)) time complexity.

Problem

Given an m x n integer matrix, where each row is sorted in non-decreasing order and the first integer of each row is greater than the last integer of the previous row, we need to determine if a given target integer is present in the matrix.

2. Solution Steps

1. Flatten the 2D matrix into a virtual 1D sorted array.

2. Apply binary search on this virtual array to find the target.

3. Calculate mid-point indices considering the 2D matrix structure.

4. Compare the target with the element at the calculated mid-point in each iteration.

5. Return true if the target is found, otherwise false.

3. Code Program

public class Search2DMatrix {
    public static void main(String[] args) {
        int[][] matrix = {
            {1, 3, 5, 7},
            {10, 11, 16, 20},
            {23, 30, 34, 60}
        };
        int target = 3;
        System.out.println(searchMatrix(matrix, target)); // Test the function
    }

    // Function to search for a target value in a 2D matrix
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;
        int m = matrix.length, n = matrix[0].length;
        int start = 0, end = m * n - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;
            int midValue = matrix[mid / n][mid % n]; // Convert 1D index to 2D coordinates

            // Binary search logic
            if (midValue == target) {
                return true;
            } else if (midValue < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return false;
    }
}

Output:

true

Explanation:

1. searchMatrix: The function implements a binary search in a 2D matrix.

2. It first checks for edge cases where the matrix is null or empty.

3. The matrix is treated as a virtual 1D array for the purpose of binary search, using the formula matrix[mid / n][mid % n] to map the mid-point index in the 1D array to coordinates in the 2D matrix.

4. Binary search is applied, where the search space is halved in each iteration based on the comparison with the target.

5. If the target is found, the function returns true; otherwise, it returns false after exhausting the search space.

6. This approach ensures a runtime complexity of O(log(m * n)), efficiently searching through the matrix.