Home » Matrix-Backtrack » 2D Matrix Search

# 2D Matrix Search

Given an n x n matrix, where every row and column is sorted in increasing order. Given a number x, how to decide whether this x is in the matrix. The designed algorithm should have linear time complexity.

2) Loop: compare this element e with x
….i) if they are equal then return its position
…ii) e < x then move it to down (if out of bound of matrix then break return false)
..iii) e > x then move it to left (if out of bound of matrix then break return false)
3) repeat the i), ii) and iii) till you find element or returned false

```
import java.util.*;

public class MatrixwithMax1
{

/* A function to find the index of first index of 1 in a boolean array arr[] */
public static int first(int arr[], int low, int high)
{
if(high >= low)
{
// get the middle index
int mid = low + (high - low)/2;

// check if the element at middle index is first 1
if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
return mid;

// if the element is 0, recur for right side
else if (arr[mid] == 0)
return first(arr, (mid + 1), high);

else // If element is not first 1, recur for left side
return first(arr, low, (mid -1));
}
return -1;
}

// The main function that returns index of row with maximum number of 1s.
public static int rowWithMax1s(int mat[][])
{
int max_row_index = 0, max = -1; // Initialize max values

// Traverse for each row and count number of 1s by finding the index
// of first 1
int i, index;
for (i = 0; i < R; i++)
{
index = first (mat[i], 0, C-1);
if (index != -1 && C-index > max)
{
max = C - index;
max_row_index = i;
}
}

return max_row_index;
}

public static void main(String[] args)
{
int mat[][] = { {0, 0, 0, 1},
{0, 1, 1, 1},
{1, 1, 1, 1},
{0, 0, 0, 0}
};

System.out.println("Index of row with maximum 1s is %d \n", rowWithMax1s(mat));

}

}

```

### Website #### arpit tak

I like JAVA . I code. I chill. I blog.I eat. I sleep. I dream.