2. b) Search a 2D Matrix

2. b) Search a 2D Matrix

Problem link :- click here
Approach ----> Binary Search

//leet code 
//APPROACH ----> BINARY SEARCH
package progams;

import java.util.Scanner;

public class Matrix__2__b
{

	/*
        		01  03  05  07
        		10  11    16  20
        		23  30  34  60
        		
        	the matrix is sorted.
        	if the elements was in a array then we would have done binary search
        	lets do the same thing here by assuming elements are in a array 
        				but the only thing is we have to convert the index of array to the index of matrix
        */
        
        static void searchSortedMatrix(int mat[][], int r, int c, int key)
        {
                int n = r*c;       //for the index of the array(assumption)
                
                int low   = 0;
                int high = n-1;
                
                int flag = 0;       // to know whether found or not
                
                while(low<=high)
                {
                	int mid = (low + high)/2;
                	
                	int i = mid / c;          //row of the mid element
                	int j = mid % c;        //column of the mid element
                	
                	if(key == mat[i][j])
                	{
                		flag = 1;
                		System.out.println("\n\nElement is found at position : (" + i +", " + j + ")");
                		return;
                	}
                	else if(key < mat[i][j])
                		high = mid - 1;
                	else
                		low = mid + 1;
                }
                
                if(flag == 0)
                	System.out.println("\n\nElement is not found");
        }
	
	public static void main(String[] args)
	{
		int i, j, r, c;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the number of rows : ");
		r = s.nextInt();
		System.out.print("Enter the numvber of columns : ");
		c = s.nextInt();
		int matrix[][] = new int[r][c];
		System.out.println("Enter the elements of the matrix : ");
		for(i=0; i<r; i++)
		{
			for(j=0; j<c; j++)
				matrix[i][j] = s.nextInt();
		}
		System.out.println("Given matrix : ");
		printMatrix(matrix, r, c);
		System.out.print("\nEnter the target to search : ");
		int target = s.nextInt();

		searchSortedMatrix(matrix, r, c, target);
	}

	static void printMatrix(int mat[][], int r, int c)
	{
		for(int i=0; i<r; i++)
		{
			for(int j=0; j<c; j++)
				System.out.print(mat[i][j] + "  ");
			System.out.println();
		}
	}
}

Time complexity :- O(log(r*c))
Space complexity :- O(1)