Searching In A Sorted 2D Array O(n)

 

Searching in a sorted 2D Array

CODE

#include<iostream>

using namespace std;

int main()

{

int i,j,target,n,m,flag=false;

cout<<"Enter rows and columns of matrix\n";

cin>>n>>m;

int arr[n][m];

cout<<"\nEnter array elements\n";

for(i=0;i<n;i++)

{

for(j=0;j<m;j++)

{

cin>>arr[i][j];

}

}

cout<<"\nEnter Element to search\n";

cin>>target;

int r=0,c=m-1;

while(r<n && c>=0)

{

if(arr[r][c]==target)

{

flag=true;

cout<<"Position= ("<<r<<","<<c<<")";

break;

}

if(target<arr[r][c])

c--;

if (target>arr[r][c])

r++;

}

if(flag)

cout<<"Found";

else

cout<<"Not Found";

return 0;

}

OUTPUT