CareerCup

Search for the element in only the first column of matrix using binary search.
Lets say if a is a n X m matrix and elem is the element, then
if a[i][0] < elem < a[i+1][0]
then do a binary search for the element in ith row between a[i][0] and a[i][m]

Lets say for this 2D matrix:
Integer[][] arr = new Integer[][]{
{1,5,20,21},
{2,6,39,40},
{3,7,40,41},
};

we write the code as:

private void haselement(int row, int column,int element){
if(row < 0 || column > 3){
System.out.println("The element does not exist " + element);
System.exit(0);
}
if(arr[row][column] == element){
System.out.println("The element exists " + element);
}else if (element < arr[row][column]){
haselement(row - 1, column, element);
}else{
haselement(row, column + 1, element);
}
}

Call it using:
obj.haselement(2,0,21);

Complexity: O(log n)
As you will search only one half of the matrix and not the whole
Where n = rows + columns

I have tried this code and it works. please correct me if I am wrong!!!!

As far as I see, this is a difficult problem. Even to traverse an array it takes O(n2) so its not simple to search an element in O(n). But I think I got some kind of solution, not sure if its O(n) though. Also one assumption we have to make is all the values below a row are greater than the current rows values. Otherwise there is no way we can find a solution less than O(n2).
Also to simplify further I considered only square matrices, since this solution is working it should not be super difficult to convert it into a non-square matrix.

My idea is search for the element on diagnol elements if not found narrow down to the two rows between which the element could exist. then perform a linear search on the rows. Since we are searching only two rows this should be O(n).

//Assuming that the matrix is square m=n
//Assuming no row i+1 has an element lower than i

The scaffold for the funtion:
 int[,] mat3 = new int[,] {   {1,2,3,4,5},
                                         {6,7,8,9,10},
                                         {11,12,13,14,15},
                                         {16,17,18,19,20},
                                         {21,22,23,24,25},
                                     };
            int[,] mat2 = new int[,] {   {1,2,3,4},
                                         {6,7,8,9},
                                         {11,12,13,14},
                                         {16,17,18,19},
                                     };
            int[] pos = p.Search2DSortedSquareMatrix(mat3, 3);
            if(pos.Lenght==2)
            Console.Write("x {0} y {1}", pos[0], pos[1]);
   
     public int[] Search2DSortedSquareMatrix(int[,] mat, int x)
        {
            int[] op=new int[2];
            int m = mat.GetLength(0);
            int mid = m/2; //1 to get ceiling
            bool minflag=false, maxflag=false;
            int x1=0,y1=0;
            while ((!minflag || !maxflag) && mid > 0 && mid < m)
            {
                if (mat[mid, mid] == x)
                {
                    op[0] = mid; op[1] = mid;
                    return op;
                }
                else if (mat[mid, mid] < x)
                {
                    minflag = true;
                    op[0] = mid;
                    mid++;
                }
                else if (mat[mid, mid] > x)
                {
                    maxflag = true;
                    op[1] = mid;
                    mid--;
                }
            }
//Linear search this loop can further be improved but I am not able to figure out now.
            for(int i=op[0];i<=op[1];i++)
                for(int j=0;j<m;j++)
                    if (mat[i, j] == x)
                    {
                        op[0] = i; op[1] = j;
                        return op;
                    }
                   
            return null;
        }

We can use an algorithm based on elimination. Let M and N be the number of rows and columns respectively. Lets start our search from Matrix[0][N]. Every time we decrement the column, we potentially eliminate all the elements below it in that particular column and every time we decrement the row, we potentially eliminate all the elements to the left of it in that row.

Bool SearchElement(int **Matrix, int element)
{
     int row = 0, col = N-1;
     while(row>M && col>0)
     {
          if(Matrix[row][col] == element)
               return true;
          else if(Matrix[row][col]>element)
               col--;
          else if(Matrix[row][col]<element)
               row++;
      }  
      return false;
}

public class Searchin2DArraySortedByRowandColumn {
public static void main(String args[]) {
int arr[][] = { { 1, 3, 5, 7, 9 }, { 2, 4, 6, 8, 10 },
{ 11, 13, 15, 17, 19 }, { 12, 14, 16, 18, 20 },
{ 21, 23, 25, 27, 29 } };

int search = 21;
int row = 0, col = arr[0].length - 1;

while (row < arr.length && col >= 0) {
if (arr[row][col] == search) {
System.out.println("Found" + row + " " + col);
break;
} else if (arr[row][col] > search) {
col--;
} else if (arr[row][col] < search) {
row++;
}
}
}
}

Can ny1 explain how the above mentioned solution will work for an array like
{{10,12,13,14},
{1,2,3,4}}
Say i were to search for element 3 - using above sol. i start by comparing with 14 and continue doing col--, till i reach 10 which is still greater the element to be found i.e 3. Now wat?

Whoaaaaaaaa
So much code for a small problem. The arrangement is called a Young's tableau.
Searching takes O(n+m), since you can eliminate only 1 row/col at any time.

The solution i think can be done in O(log(n)+log(m))=> O(log(n)) if n==m
first apply binary search on diagonal elements . wherever we get a[i][i]>Key
then search in those corresponding row as well as column using again Binary Search.
Correct me if m wrong.