Staircase search

#1

I am not getting the idea how to solve it. Help me with this.

#2

Hey @ankita_10
Here’s the algo for this:

Let x = element we’re trying to search for in the matrix,
….e = current element we’re processing in the array.

  1. Start with top right element.
  2. Loop: compare this element e with x
    …i) if e = x, then return position of e, since we found x in the given matrix.
    …ii) if e > x then move left to check elements smaller than e (if out of bound of matrix, then break and return false)
    …iii) if e < x then move below to check elements greater than e (if out of bound of matrix, then break and return false)
  3. repeat the i), ii) and iii) until you find the element or return false

and here’s the explanation for it:
Let’s start our search from the top-right corner of the array. There are three possible cases.

  1. The number we are searching for is greater than the current number. This will ensure, that all the elements in the current row is smaller than the number we are searching for as we are already at the right-most element and the row is sorted. Thus, the entire row gets eliminated and we continue our search on the next row. Here elimination means we won’t search on that row again.

  2. The number we are searching for is smaller than the current number. This will ensure, that all the elements in the current column is greater than the number we are searching for. Thus, the entire column gets eliminated and we continue our search on the previous column i.e. the column at the immediate left.

  3. The number we are searching for is equal to the current number. This will end our search.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.