mohammad.z.siddiqui
BAN USERI am a Junior in Computer Science at Purdue University. I have interned at Infosys(2007) and Intel (2008). If any questions you can email me at zeeshan@purdue.edu
This can be done in O(nlogn). The following has to be done for every node. Pick a node and then find if it is a right node or a left node, if it happens to be a right node make sure it is greater than its parent, then compare this node with its parent's parent based on its parent being a left node or a right node of its grandparent. This process goes on till it reaches the root node. So for every node u take logn steps and for all the node its it will take nlogn.
- mohammad.z.siddiqui October 19, 2008P < R/(2*R)
- mohammad.z.siddiqui October 19, 2008A simple solution to this problem is in O(n). Consider the fact that the matrix is a square matrix NxN and all of its rows and column are sorted. All we need to do is move diagonally across the matrix and see if the element is smaller than S then we move further diagonally . When we see that "S" is smaller than one of the diagonal element then we check in that diagonal element's row and column to see if S exists.
void check(int **a, int n, int S){
int i=0;
while(i<n){
if(a[i][i] == S){
printf("\n found at %d , %d",i,i);
}
else if(a[i][i] < S)
i++;
else {
for(int j=0;j<i;j++){
if(a[i][j] == S)
printf("\n found at %d , %d",i,j);
else if(a[j][i] == S)
printf("\n found at %d , %d",j,i);
}
}
}
printf("\nNot Found!");
}
You need to modify the binary search little bit such that the if the middle element happens to be a 0 then if the number right next to it is 1 then u conclude that is the first one else if the middle number happens to be a 1 then if the number left to it is a 0 then u can conclude its the first one...if none of these is the case then u recurse the same process of the left half if the middle number happens to be a one or the right half if the number happens to be a zero. Its technically Binary search paradigm . Hope that helps.
- mohammad.z.siddiqui October 20, 2008