Search an Element in a Sorted 2D Matrix - Java Solution

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

1. Introduction

In this post, we'll explore an efficient algorithm to search for a value in a sorted 2D matrix using Java. This problem is a great example of applying binary search in a two-dimensional context, considering the sorted nature of the matrix.

Problem

Given an m x n matrix where each row is sorted from left to right and the first integer of each row is greater than the last integer of the previous row, write an algorithm to search for a target value within this matrix.

Examples:

Input:

matrix = [

[1, 5, 9, 11],

[13, 16, 19, 24],

[28, 30, 38, 50]

],

target = 5

Output: true

Input:

matrix = [

[1, 5, 9, 11],

[13, 16, 19, 24],

[28, 30, 38, 50]

],

target = 12

Output: false

2. Solution Steps

1. Treat the 2D matrix as a flattened 1D array and apply binary search.

2. Calculate the middle element's row and column using index manipulation.

3. Compare the target with the middle element and adjust the search range accordingly.

4. Continue this process until the target is found or the search space is exhausted.

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

3. Code Program

public class Solution {
    public static void main(String[] args) {
        int[][] matrix1 = {
            {1,  5,  9,  11},
            {13, 16, 19, 24},
            {28, 30, 38, 50}
        };
        int target1 = 5;

        int[][] matrix2 = {
            {1,  5,  9,  11},
            {13, 16, 19, 24},
            {28, 30, 38, 50}
        };
        int target2 = 12;

        System.out.println("Target " + target1 + " found: " + searchMatrix(matrix1, target1));
        System.out.println("Target " + target2 + " found: " + searchMatrix(matrix2, target2));
    }

    // Method to search the matrix
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false; // Check for empty matrix

        int rows = matrix.length, cols = matrix[0].length;
        int low = 0, high = rows * cols - 1;

        // Binary search
        while (low <= high) {
            int mid = low + (high - low) / 2; // Calculate mid index
            int midValue = matrix[mid / cols][mid % cols]; // Convert 1D index to 2D coordinates

            if (midValue == target) { // Check if midValue is the target
                return true;
            } else if (midValue < target) { // Adjust search range
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return false; // Target not found
    }
}

Output:

Target 5 found: true
Target 12 found: false

Explanation:

In the first example, the target 5 is present in the matrix, so the output is true. The algorithm flattens the matrix into a virtual 1D array and applies binary search. 

For the second example, target 12 is not in the matrix, resulting in a false. This method efficiently searches the matrix with a time complexity of O(log(mn)), where m and n are the dimensions of the matrix.

My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:

Build REST APIs with Spring Boot 4, Spring Security 7, and JWT

🆕 High-Demand 80–90% OFF

[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25

🆕 High-Demand 80–90% OFF

ChatGPT + Generative AI + Prompt Engineering for Beginners

🚀 Trending Now 80–90% OFF

Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Building Real-Time REST APIs with Spring Boot - Blog App

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Building Microservices with Spring Boot and Spring Cloud

🌟 Top Rated 80–90% OFF
Available in Udemy for Business

Java Full-Stack Developer Course with Spring Boot and React JS

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Build 5 Spring Boot Projects with Java: Line-by-Line Coding

🌟 Top Rated 80–90% OFF

Testing Spring Boot Application with JUnit and Mockito

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Spring Boot Thymeleaf Real-Time Web Application - Blog App

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Master Spring Data JPA with Hibernate

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Spring Boot + Apache Kafka Course - The Practical Guide

🎓 Student Favorite 80–90% OFF
Available in Udemy for Business

Java Testing: Mastering JUnit 5 Framework

🆕 New 80–90% OFF

Reactive Programming in Java: Spring WebFlux and Testing

🌟 Top Rated 80–90% OFF

Spring Boot + RabbitMQ Course - The Practical Guide

🌟 Top Rated 80–90% OFF
Available in Udemy for Business

Functional Programming in Java (Includes Java Collections)

🎓 Student Favorite 80–90% OFF

ChatGPT for Java Developers: Boost Your Productivity with AI

🚀 Trending Now 80–90% OFF