assume number is to found is n
this O(logn) solution
solution 2:
1 apply binary search on diagonal which return position (which element is
just greater then n) let supose return i;
2
int j1=binary(arr,i,N-1); // search in above row
if(j1!=-1) {printf(%d ,%d,i,j1);}
int
-- Forwarded message --
From: subramania jeeva subramaniaje...@gmail.com
Date: Thu, Sep 23, 2010 at 7:53 AM
Subject: Re: MICROSOFT INTERNSHIP (Coding round)
To: mitcse08i...@googlegroups.com
Also in placement the question asked was
Given a 2 dimensional matrix
-- Forwarded message --
From: sivaviknesh s sivavikne...@gmail.com
Date: Mon, Jul 18, 2011 at 11:29 PM
Subject: Fwd: MICROSOFT INTERNSHIP (Coding round)
To: algogeeks@googlegroups.com
-- Forwarded message --
From: subramania jeeva subramaniaje...@gmail.com
Date:
start from top right corner... if a[i][j] x then move left, else if
a[i][j] x then move down and if a[i][j] == x then print i and j
On Mon, Jul 18, 2011 at 11:30 PM, sivaviknesh s sivavikne...@gmail.comwrote:
-- Forwarded message --
From: sivaviknesh s
O(m+n) start at bottomleft corner. If target value is found value move
right , if less move above else uve got the number.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To
A more efficient approach :
Suppose the array is M*N
i=j=0;
if(a[i][j] == x)
return;
mid1=(i+M-1)/2;
mid2=(j+N-1)/2;
if(a[i][mid1]==x || a[mid2][j])==x
if(abs(a[i][mid1] - x) abs(a[mid2][j]) - x)
--
You received this message because you are subscribed to the Google Groups
Algorithm
Sry for the above typo. Correct algo
A more efficient approach :
Suppose the array is M*N
fun(int i, int j)
if(a[i][j] == x)
return;
mid1=(i+M-1)/2;
mid2=(j+N-1)/2;
if(abs(a[i][mid1] - x) abs(a[mid2][j]) - x)
return fun(i,mid1)
else
return fun(mid2,j)
This algo can be easily
start from middle element of first column..perform directed binary search
either in corresponding column or row.
On Mon, Jul 18, 2011 at 11:52 PM, ankit sambyal ankitsamb...@gmail.comwrote:
Sry for the above typo. Correct algo
A more efficient approach :
Suppose the array is M*N
fun(int i,
