CareerCup

Solution to this question is given some where in this forum.
idea was to bst technique starting from leftmost-bottom cell of grid.

this can be done in O((no_rows + no_colums)-1) in worst case when the element which we are looking is in top - most row, and last column.

Can you explain how?

int search(int arr[5][5],int x, int y, int num)
{
int found=0;

while(x>=0 && y<5)
{
complexity++;
if( arr[x][y]==num)
{
found=1;
break;
}
else if(arr[x][y]>num)
{
x--;
}
else
{
y++;
}


}

return found;
}

How abt this....

First check if the element is <> A[n,n/2]. If its greater then we conclude that its in the right half the matrix (all rows, but columns greater than n/2 ). Else in the left half. (how ?? )
Now, assume that the given element is in the greater half, then check at <> A[n/2, n]. (if in left then check at A[n/2,n/2] ) We get a partition on both the sides.

It looks like
T[n] = 2 + T[n/4]. Which may spew out (log n)^2 ( a little rusty there ).

Thing left out - way to figure how to write smart breakpts.

k, I was wrong in forming the recursive equation. But the final complexity looks fine to me.

Another way is to find the right row where the element can be found. Then search in that row if the element is present or not.

Say given Arr is:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

First search on the last col to decode the right row. To decide the right row:
check if the arr element is < num( to be found) then check with the next row last element.
if Equal then found.
if Arr element > num, then this is the right row.

Then search the elements in that row. Use Binary search to search in a row. Then we can solve the prob in O(n) + O(logn) in the worst case.

A 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!");
}

Should we use quick-selection algorithm to solve this problem ?

We have to traverse the diagonal till we find a diagonal element b bigger than S. This will mean that earlier diagonal element a is smaller than S. Thus S lies in the column below a or column above b.
For eg. in matrix:
23 45 67 89
24 56 89 99
35 66 92 98
36 47 93 100
...suppose S is 89. Now we move through diagonal 23,56,92,100. We can say 89 lies between 56 and 92. Thus it lies in column below 56 or above 92.
This is in O(n)!

I can do this in log(n).

use binary search to try to find the target value T in the last column. If found, return. Otherwise, check last position of the pointer of the binary search and the row that includes T can be easily determined. Search in that row use binary search to find T.

how about Binary search on the diagonal...

can we do it like this:
we compare S with bottom left element and top right element:
if S<both compare S with the upper diagonal
if S>both compare S with lower diagonal
else look for S in the same diagonal
this should be in O(n).
what say ?

At any stage, the top-left(0,0) is the smallest no in the matrix and bottom-right(n,n) is the largest.

Compare X to check if it lies in this range of smallest-largest no. If Yes, reduce space to a n-1 * n-1 matrix and compare with its smallest and largest no.

Continue reducing the space until X falls out of the range.
So,
1st iteration = n*n matrix
2nd iteration = (n-1) * (n-1) matrix
3rd iteration = (n-2) * (n-2) matrix and so on.

This would be O(n).

this question has been answered hell of times in this forum and as I remember the best and smartest answer was from LOLer with the complexity of O(rowCount+ colCount-1) as already mentioned by "Anonymous on October 14, 2008"

#include <iostream>

using namespace std;
/*
 * type 1 : 1 2 3  4 5 6  7 8 9
 * type 2 : 1 5 10 2 6 11 3 7 12
 */
int search(int a[][3], int e) {
    int left = 0;
    int n = 3;
    int right = n * n - 1;
    int mid = 0;
    int val = 0;
    bool is_type1 = false;
    for (int i = 0; i < n - 1; i++) {
        if (a[i][i + 1] == a[i + 1][i]) {
            continue;
        }
        is_type1 =  (a[i][i + 1] < a[i + 1][i]);
    }
    
    while (left <= right) {
        mid = (left + right) / 2;
        if (is_type1) {
            val = a[mid / n][mid % n];
        } else {
            val = a[mid % n][mid / n];
        }
        
        if (val == e) {
            return true;
        } else if (val < e) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}


int main() {
    //int a[][3] = { {1, 5, 10}, {2, 6, 11}, {3, 7, 12} };
    //int a[][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };
    //int a[][3] = { {1, 5, 10}, {5, 11, 12}, {10 , 13, 14} };
    int a[][3] = { {1, 5, 10}, {5, 11, 12}, {10, 12, 13} };

    for (int i = -1; i < 15; i++) {
        if (search(a, i)) {
            cout << i << endl;
        }
    }
    return 0;
}

having some problems posting. ignore this if u have the proper version.
sorry for the confusion.

bool search(int a[][5], int n, int e) {
    int left = 0;
    int right = n * n - 1;
    int mid = 0;
    int val = 0;
    
    while (left <= right) {
        mid = (left + right) / 2;
        val = a[mid / n][mid % n];
        if (val == e) {
            return true;
        } else if (val < e) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    left = 0;
    right = n * n - 1;
    while (left <= right) {
        mid = (left + right) / 2;
        val = a[mid % n][mid / n];
        if (val == e) {
            return true;
        } else if (val < e) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}