GO Classes DPP | Algorithms | Searching

Answer 1

This task can be done in $\theta(n)$ time using the following approach:
We have an $n \times n$ matrix:

• Each row is sorted in ascending order (left $\rightarrow$ right).
   
• Each column is sorted in ascending order (top $\rightarrow$ bottom).
   
• Start from the top-right corner (row = 0, col = n-1).
   
• Compare with target x. .

Rules:

1. If $\operatorname{arr}[\mathrm{row}][\mathrm{col}]==x \rightarrow$ Found.

2. If $\operatorname{arr}[\mathrm{row}][\mathrm{col}]>x \rightarrow$ Move left (col--).

3. If arr[row][col] $<x \rightarrow$ Move down (row++).

In the worst case:

• We move $n-1$ steps down and $n-1$ steps left.
   
• Total $=2(n-1)$ steps $=\Theta(n)$.

Comments

Got it!

Answer 2

N*N Matrix are Sorted in Both Direction

Then Use  Bineary Serch for First Col. and Then Row

For Row Log(n)+ For Coloum  Log(n)

O(Log n)

A is correct Answer

Answer 3

answer is B  for sigle n array it take log n then for n2 it will take n  because in worst case scenario we have to traverse through n columns or rows