Searching for an element in a 2-d sorted array sortedarray array searching    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: 5 years ago 0 0 Edit 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;}