Searching for an element in a 2-d sorted array
  • Posted: 5 years ago
  • Updated: 4 years ago
  • Edit
  • answers (1)
  • views (2259)

You are given a 2 dimensional array of size (\( N \times N \)). Each row and column are sorted in ascending order. How would you find an element in it?


Posted Answers

The algorithm works as :


  • Start from the last element of the first row ( array[0][N-1] ).
  • If the element matches with the element we are looking for, return true.
  • If the element is greater than the element we are looking for, go to the element at previous column but same row.
  • If the element is less than the element we are looking for, go to the element at next row but same column.
  • Return false if the element is not found after reaching the element at the last row of first column( array[N-1][0] ).

Running time = \( O(N) \).

public boolean FindElementIn2DArray(int[][] array, int k, int r, int c){

int row = 0;
int column = 0;

while(row < r & & column >= 0){
if(array[row][column] == k)
return true;
elseif(array[row][column] > k)
column--;
else
row++;
}
return false;
}

You need to Sign In to post your solution.