CareerCup

The idea is to use quaternary search tree so the complexity T(m*n) = 3 * T(m*n/4) + c it results in O((m*n)^log 3 base 4) complexity - it is not the best result available, see below discussion for a better result

#include <iostream>
#include <cassert>

bool searchHelper(int v, int* a, int n) {
    if (a[0] > v || a[n-1] < v)
        return false;

    int cx = n / 2;
    if (a[cx] == v)
        return true;
    return (a[cx] < v) ? searchHelper(v, a + cx + 1, n - cx - 1 ) : searchHelper(v, a, cx);
}

bool searchHelper(int v, int* a, int m, int sx) {
    if (a[0] > v || a[(m-1) * sx] < v)
        return false;

    int cy = m / 2;
    if (a[cy * sx] == v)
        return true;
    return (a[cy * sx] < v) ? searchHelper(v, a + (cy + 1) * sx, m - cy - 1, sx ) : searchHelper(v, a, cy, sx);
}

bool searchHelper(int v, int* a, int n, int m, int sx) {
    if (n == 1 && m == 1)
        return a[0] == v;
    if (a[0] > v || a[n-1 + (m-1) * sx] < v)
        return false;

    if (m == 1) // binary search{
        return searchHelper(v, a, n);
    if (n == 1)
        return searchHelper(v, a, m, sx);

    int cx = n / 2;
    int cy = m / 2;
    int p = a[cx + cy * sx];

    if (p == v)
        return true;

    if (p > v) {
        return searchHelper(v, a, cx, cy, sx)
                || searchHelper(v, a + cx, n - cx, cy, sx)
                || searchHelper(v, a + cy * sx, cx, m - cy, sx);
    }
    else
        return searchHelper(v, a + (cx + 1) + (cy + 1) * sx, n - cx - 1, m - cy - 1, sx)
                || searchHelper(v, a + cx + 1, n - cx - 1, cy + 1, sx)
                || searchHelper(v, a + (cy + 1) * sx, cx + 1, m - cy - 1, sx);
}

int main()
{
    int a[4][4] = {{1,14,25,35},
                   {2,16,28,38},
                   {5,20,28,40},
                   {16,22,38,41}};
    bool found = true;
    for (int i=0; i< 4; ++i)
        for (int j=0; j< 4; ++j) {
            bool res = searchHelper(a[i][j], &a[0][0], 4, 4, 4);
            found = found & res;
        }

    assert(found);
    assert(!searchHelper(3, &a[0][0], 4, 4, 4));
    return 0;
}

Short answer "Saddleback Search"

This is a sorted matrix, i.e., the rows and columns are sorted, so you can take advantage of that.

You can either start from the top-right M[0][n-1]
While until key found in M
Let M[i][j] be the current element
if M[i][j] < key, go down (M[i+1][j])
else if M[i][j] > key, go to left (M[i][j-1])

Or you can start from bottom left M[n-1][0]
While until key found in M
Let M[i][j] be the current element
if M[i][j] < key, go to right (M[i][j+1])
else if M[i][j] > key, go up (M[i-1][j])

Total running time is O(n)

Binary search o(log(m)*log(n))

binarySearch( matrix M, rows n, columns m, value v){
	
	// Binary search the rows
	nLow = 0, nHigh = n-1
	while(nLow <= nHigh ){
		nMid = (nLow + nHigh)/2
		
		// Binary search through a column
		mLow = 0, mHigh = m-1
		while(mLow <= mHigh){

			mMid = (mLow + mHigh)/2
			if (v < M [nMid] [mMid])
				mHigh = mMid-1
			else if (v > M [nMid] [mMid])
				mLow = mMid+1
			else 
				return 1
		}
		
	// TODO: Figure out how to change nHigh and nLow
	
	/*
	* I got stuck here and I have to go to bed but this is what i have so far!
	*/
	}
}

search rows

in order to achieve better complexity we can iterate rows
and for each row do a binary search in their colums O( n * log(m) )

The algorithm works using elimination of rows and columns and its worst case complexity is O(n+m), where <n> is the count of rows and <m> is the count of columns.
Solution:
When moving left we eliminate all the values below that column.
Similarly, when moving down we eliminate all the elements to the left
of that cell in the current row.

bool find_int(int mat[][], int rows, int cols, int val)
{
    int n = 0; // row index
    int m = cols - 1; // column index
    
    while(m >= 0 && n < rows){
        int curval = mat[n][m];
        if (curval == val) {
            printf("found at: %-3d %-3d\n", n, m);
            return true;
        }
        else if (curval > val)
            --m;
        else
            ++n;    
    }
    
    return false;
}

public static void main(String[] args) {
		int a[][] = { { 1, 14, 25, 35 }, { 2, 16, 28, 38 }, { 5, 20, 28, 40 },
				{ 16, 22, 38, 41 }};
		int noToFind = 41;
		boolean found = false;
		int foundi = 0;
		int foundj = 0;
		System.out.println(a.length);
		System.out.println(a[0].length);
		for (int i = 0; i < a.length; i++) {
			if (a[i][0] < noToFind && a[i][a[i].length-1] < noToFind) {
				continue;
			} else if (a[i][0] < noToFind && a[i][a[i].length-1] >= noToFind) {
				for (int j = 0; j < a[i].length; j++) {
					if (a[i][j] == noToFind) {
						found = true;
						foundi = i;
						foundj = j;
						break;
					}
				}
			}
			if (found == true) {
				break;
			}
		}
		System.out.println("foundi -- "+foundi);
		System.out.println("foundj -- "+foundj);
	}

I have tried implementing the quareternary search

void quarternary_search(int a[][5],int r_begin,int r_end,int c_begin,int c_end,int x)
{
    if (r_begin>r_end || c_begin>c_end)
        return;
    if (r_begin==r_end==c_begin==c_end)
    {
        if(x==a[r_begin][r_end])
        {
            std::cout<<"\nMatch found:";
            return;
        }
        else
        {
            std::cout<<"\nMatch not found:";
            return;
        }
    }
    int r_mid=(r_begin+r_end)/2;
    int c_mid=(c_begin+c_end)/2;

    if (r_mid<r_begin || r_mid>r_end || c_mid<c_begin || c_mid>c_end)
        return;

    if(a[r_mid][c_mid]==x)
        std::cout<<"\nMatch Found:";
    else
    {
        int x1=abs(a[r_begin][c_begin]-x);
        int x2=abs(a[r_begin][c_mid]-x);
        int x3=abs(a[r_mid][c_begin]-x);
        int x4=abs(a[r_mid][c_mid]-x);
        if(x1==0 || x2==0 || x3==0 || x4==0)
        {
            std::cout<<"\nMatch Found:";
            return;
        }
        if(x1<x2 && x1<x3 && x1<x4)
            quarternary_search(a,r_begin,r_mid-1,c_begin,c_mid-1,x);
        else if(x2<x4 && x3<x4)
            quarternary_search(a,r_begin,r_mid,c_mid,c_end,x);
        else if (x3<x4)
            quarternary_search(a,r_mid,r_end,c_begin,c_mid-1,x);
        else
            quarternary_search(a,r_mid,r_end,c_mid,c_end,x);
    }
    return;
}

Can we move along the diagonal (log (n))till we exceed the search value. ? Then wecan move along the row or column (depending on the max (m, n)? This solution is log (m) + log (n)

//// Split the matrix into 4 rectangles along the diagonals and recursively search through ///  left bottom and right top
#include<iostream>
#include<cstdlib>
#include<algorithm>

#define p(x) std::cout<< #x" : " << x << "\n"

int count,tra;

class Coordinate
{
        public:
        int x;
        int y;
        Coordinate( int X=0, int Y=0):x(X),y(Y){}
        Coordinate operator+(int add){ x += add; y += add ; return *this; }
        Coordinate operator-(int add){ x -= add; y -= add ; return *this; }
        ///void operator=(Coordinate& c) {this->x = c.x ; this->y = c.y }
        bool isBefore(Coordinate& p) { return (this->x <= p.x && this->y <= y );}
        void setToAverage( Coordinate& b, Coordinate& e) { this->x = (b.x+e.x)/2 ; this->y = (b.y+e.y)/2 ;}
        bool inBound(Coordinate& end) { return ( this->x >=0 && this->x <= end.x && this->y >= 0 && this->y <= end.y ); }
        bool isValid() { return !(this->x == -1 && this->y == -1 ); }

        friend std::ostream& operator << (std::ostream& o, Coordinate& p);
};

Coordinate traverse(int **mat, int ele, Coordinate beg, Coordinate end, Coordinate matEnd)
{
        Coordinate start(beg.x,end.y);

        ///p(start);
        while ( start.inBound(matEnd) )
        {
                if ( mat[start.x][start.y] == ele )
                        return start;
                else if ( ele < mat[start.x][start.y])
                        start.y -= 1;
                else
                        start.x += 1;
                        //start = start - 1;
                ///p(start);
                tra++;
        }
        return Coordinate(-1,-1);
}

std::ostream& operator << (std::ostream& o, Coordinate& p)
{
        o << "(x,y) : ( " << p.x << " , " << p.y << ") \n";
        return o;
}

Coordinate lookUpElement(int **mat, Coordinate begin, Coordinate end, Coordinate matEnd,int element);
Coordinate binarySearch(int **m, int fixedIndex, int beg, int end, bool isRow, int element);

Coordinate partitionAndSearch(int **mat, Coordinate begin, Coordinate end, Coordinate pivot ,int element, Coordinate matEnd)
{

        Coordinate lowerLeftBegin ( pivot.x, begin.y), lowerLeftEnd( end.x, pivot.y-1 );
        Coordinate lower = lookUpElement(mat,lowerLeftBegin, lowerLeftEnd, matEnd,element);
        p(lowerLeftBegin);
        p(lowerLeftEnd);
        if ( lower.isValid() )
        {
                return lower;
        }
        Coordinate upperRightBegin ( begin.x, pivot.y), upperRightEnd( pivot.x-1, end.y );
        p( upperRightBegin );
        p( upperRightEnd );
        return lookUpElement(mat, upperRightBegin, upperRightEnd , matEnd,element);
}
/*
        10      20      30      40      50
        100     200     300     400     500
        1000    1020    1030    1040    1050
        1031    1040    1050    1060    1090
*/

Coordinate lookUpElement(int **mat, Coordinate begin, Coordinate end, Coordinate matEnd,int element)
{
        count++;
        if ( !begin.inBound(matEnd) || !end.inBound(matEnd) )
        {
                return Coordinate(-1,-1);
        }
        else if ( mat[begin.x][begin.y] == element )
        {
                return begin;
        }
        else if ( mat[end.x][end.y] == element )
        {
                return end;
        }
        else if ( !begin.isBefore(end))
        {
                return Coordinate(-1,-1);
        }
        int diagDistance = std::min( abs(begin.x - end.x), abs(begin.y-end.y));
        p(diagDistance);
        p(begin);
        p(end);
        #ifndef OPTIMIZE
        if ( !diagDistance )
        {
                bool isRow ( begin.x == end.x );
                Coordinate o =binarySearch(mat, isRow ? begin.x : begin.y  , isRow ? begin.y : begin.x , isRow ? end.y : end.x, isRow, element );
                if ( o.isValid() )
                        return o;
        }
        #endif
        Coordinate start(begin),p;
        Coordinate last(begin.x+diagDistance, begin.y + diagDistance );


        while( start.isBefore(last) )
        {
                p.setToAverage(start,last);
                if ( element > mat[p.x][p.y] )
                {
                        start = p + 1;
                        ///p(start);
                }
                else
                {
                        last = p - 1;
                        //p(last);
                }
                count++;
        }
        //p( start );
        return partitionAndSearch(mat,begin,end,start,element,matEnd);
}
Coordinate binarySearch(int **m, int fixedIndex, int beg, int end, bool isRow, int element)
{
        count++;
         if ( beg > end )
              return Coordinate(-1,-1);
         int mid = beg + (end-beg)/2;
         int chekElement = isRow ? m[fixedIndex][mid] : m[mid][fixedIndex];

         if ( chekElement == element )
               return ( !isRow ? Coordinate( mid, fixedIndex) : Coordinate(fixedIndex, mid) );
         else if ( chekElement >  element)
               return binarySearch(m, fixedIndex, beg, mid-1, isRow, element);
         else
                return binarySearch(m,fixedIndex, mid+1, end, isRow, element);
}

/// To search call :
Coordinate res = lookUpElement(m, Coordinate(), Coordinate(N-1,N-1), Coordinate(N-1,N-1), key);
 if ( res.isValid() )
{
    std::cout << "element found at " << res ;
}

Why not do a binary search along the diagonal until we find the bounds around the key and then do a linear search in a 2x2 matrix?

bool search(int [,] a , int num)
{
int ncol = a.GetLenght(0);
int nrow = a.GetLenght(1);
int j=0;
int i =0;
int k =0;
bool ans = false;
while( i < ncol)
{
if(a[i][j] == num)
{
ans = true;
return;
}
j++;
i++;
k++;
if(i == ncol-1 && j == nrow-1){ return;}
if(i == ncol-1 ){ i =0;}
}
}

I did this algorithm based in the next rules:
a matrix have corners (0,0) and (n,m)
if you have a matrix of 1x1 dimension check if the number is that cell.
if number < (0,0) ---> we know the number is not in the matrix.
if number > (n, m) ---> we know the number is not in the matrix.
I divide the matrix in 4 submatrix and do recursion wich each of them.

#!/usr/bin/perl
#
# search an element in a double sorted table
#
#
#
#
use warnings;
use strict;

#-------------------------------------------------------------------------------
sub table_fill
{
  my $t = shift;
  my $r = shift;
  my $c = shift;

  my $i = 0;
  my $j = 0;

  for($i = 0; $i < $r; ++$i){
    for($j = 0; $j < $c; ++$j){
      $t->[$i][$j] = ($i + 1) * 10 + $j;
    }
  }
}
#-------------------------------------------------------------------------------
sub table_print
{
  my $t = shift;
  my $r = shift;
  my $c = shift;

  my $i = 0;
  my $j = 0;
  print " table_print {\n";
  for($i = 0; $i < $r; ++$i){
    print "  ";
    for($j = 0; $j < $c; ++$j){
      print " ".(@$t)[$i][$j];
    }
    print "\n";
  }
  print " }\n";
}

#-------------------------------------------------------------------------------
#
# log(rows+columns)
#
sub table_search
{
  my $t = shift;
  my $rows = shift;
  my $columns = shift;
  #submatrix
  my $r1 = shift;
  my $c1 = shift;
  my $r2 = shift;
  my $c2 = shift;
  
  my $x = shift; #number to search
  my $n = shift; #iterations

  my $tab = '';

  #check if we are out of the matrix
  if( $r1 >= $rows ||
      $r2 >= $rows ||
      $c1 >= $columns ||
      $c2 >= $columns )
  {
    print " out of matrix [$rows, $columns] ($r1,$c1) ($r2,$c2)\n";
    return;
  }

  foreach my $i (0..$n) {
    $tab .= ' ';
  }

  print "$tab ($r1, $c1) $t->[$r1][$c1]  ($r2, $c2) $t->[$r2][$c2] ";

  if( ($r1 == $r2 ) && 
      ($c1 == $c2 )
    )
  {
    if( $x == $t->[$r1][$c1] )
    {
      print " t[$r1][$c1] == $x <==== FOUNDED in $n iterations\n";
      return;
    }
    print "\n";  
    return;
  }

  #check if $x is in the left of the table
  if( $x < $t->[$r1][$c1] )
  {
    print "sub matrix descarted $x < $t->[$r1][$c1]\n";
    return;
  }

  #check if $x is in the right of the table
  if( $x > $t->[$r2][$c2] )
  {
    print "sub matrix descarted $x > $t->[$r2][$c2]\n";
    return;
  }

  print "\n";

  my $pivot_r = int( ($r1 + $r2) / 2 );
  my $pivot_c = int( ($c1 + $c2) / 2 );

  table_search($t ,$rows, $columns
    , $r1          , $c1          , $pivot_r, $pivot_c, $x, $n + 1);

  table_search($t ,$rows, $columns
    , $r1          , $pivot_c + 1 , $pivot_r, $c2     , $x, $n + 1);

  table_search($t ,$rows, $columns
    , $pivot_r + 1 , $c1          , $r2     , $pivot_c, $x, $n + 1);

  table_search($t ,$rows, $columns
    , $pivot_r + 1 , $pivot_c + 1 , $r2     , $c2     , $x, $n + 1);
}
#-------------------------------------------------------------------------------
sub table_search_all
{
  my $t = shift;

  my $rows = 10;
  my $columns = 20;

  table_fill($t ,$rows,$columns);
  table_print($t,$rows,$columns);

  my $i = 0;
  my $j = 0;
  print " table_search_all {\n";
  for($i = 0; $i < $rows; ++$i){
    for($j = 0; $j < $columns; ++$j){
      print " searching $t->[$i][$j] : \n";
      table_search($t, $rows, $columns,0,0,$rows - 1, $columns - 1,$t->[$i][$j],0);
    }
  }
  print " }\n";
}
#-------------------------------------------------------------------------------
sub main
{
  my @t;

  print "search and element in a double sorted table\n";
  table_search_all(\@t);

}
#-------------------------------------------------------------------------------
main();

Assuming the standard rows and columns sorted property, you cannot do better than O(n+m). There are known proofs. People doing binary search etc should try proving the correctness of their algorithm once in a while.

This can be done the time of log(m)+log(n) by doing a binary search on first row and identifying the column to go further and finding a binary search for the column

I think it can be solved in 0(logm+logn) time with extra space of o(m) + o(n).
We need to apply a modified binary search in this problem both rowwise and columnwise.
Posting the solution soon.