After 1:35:00 in webinar

#1

i m not able to undrstand the staircase search @S18ML0016

#2

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.
    Since, at each step, we are eliminating an entire row or column, the time complexity of the search becomes O(n).