1) Input matrix[n][n] and element e

2) Start with top right element

i
= 0; j= n-1;

3) while termination condition:

a)
if matrix[i][j]==e;

Return
position

b)
matrix[i][j]<e then move it to down (i++)

c)
matrix[i][j]>e then move it to left (j--).

Repeat a, b and c.

**Terminating conditions:**

**1. element e found.**

2.
i>=row or j<0

public class SearchSortMat {

**private**

**static**

**void**

**findElement(**

**int**

**[][] matrix,**

**int**

**element) {**

**int**

**row = matrix.**

**length**

**;**

**int**

**i = 0;**

**int**

**j = matrix[0].**

**length**

**-1;**

**while**

**(i<row && j>=0) {**

**if**

**(element == matrix[i][j]) {**

**System.**

*out***.println(element+**

**" found at ("**

**+i+**

**","**

**+j+**

**")"**

**);**

**break**

**;**

**}**

**else**

**if**

**(element>matrix[i][j]) {**

**i++;**

**}**

**else**

**{**

**j--;**

**}**

**}**

**if**

**(i>=row || j<0) {**

**System.**

*out***.println(element +**

**" not found !!"**

**);**

**}**

**}**

public static void main(String[] args) {

int[][] matrix = {{20, 30, 40, 50},

{25,
35, 45, 55},

{37,
39, 47, 58},

{42,
43, 49, 60}};

int element = 43;

*findElement*(matrix, element);

}

}

**Time Complexity**: O(n)

## No comments:

## Post a Comment