Busque en una array 2D ordenada por filas y columnas utilizando el algoritmo Divide and Conquer – Part 1

Dada una array nxn, donde cada fila y columna se ordenan en orden creciente. Dada una clave, cómo decidir si esta clave está en la array. 
Una complejidad de tiempo lineal se discute en la publicación anterior. Este problema también puede ser un muy buen ejemplo para los algoritmos de divide y vencerás . El siguiente es el algoritmo divide y vencerás.
1) Encuentra el elemento del medio. 
2) Si el elemento central es el mismo que el retorno de la tecla. 
3) Si el elemento del medio es menor que la clave, entonces 
….3a) busque la subarray en el lado inferior del elemento del medio 
….3b) Busque la subarray en el lado derecho del elemento del medio 
4) Si el elemento del medio es mayor que la clave, entonces 
….4a) buscar subarray vertical en el lado izquierdo del elemento medio 
….4b) subarray de búsqueda en el lado derecho.
 

Después de la implementación del algoritmo anterior. 
 

// C++ program for implementation of
// divide and conquer algorithm
// to find a given key in a row-wise
// and column-wise sorted 2D array
#include<bits/stdc++.h>
#define ROW 4
#define COL 4
using namespace std;
 
// A divide and conquer method to
// search a given key in mat[]
// in rows from fromRow to toRow
// and columns from fromCol to
// toCol
void search(int mat[ROW][COL], int fromRow, int toRow,
                    int fromCol, int toCol, int key)
    {
        // Find middle and compare with middle
        int i = fromRow + (toRow-fromRow )/2;
        int j = fromCol + (toCol-fromCol )/2;
        if (mat[i][j] == key) // If key is present at middle
        cout<<"Found "<< key << " at "<< i <<
                            " " << j<<endl;
        else
        {
            // right-up quarter of matrix is searched in all cases.
            // Provided it is different from current call
            if (i != toRow || j != fromCol)
            search(mat, fromRow, i, j, toCol, key);
 
            // Special case for iteration with 1*2 matrix
            // mat[i][j] and mat[i][j+1] are only two elements.
            // So just check second element
            if (fromRow == toRow && fromCol + 1 == toCol)
            if (mat[fromRow][toCol] == key)
                cout<<"Found "<< key<< " at "<<
                            fromRow << " " << toCol<<endl;
 
            // If middle key is lesser then search lower horizontal
            // matrix and right hand side matrix
            if (mat[i][j] < key)
            {
                // search lower horizontal if such matrix exists
                if (i + 1 <= toRow)
                search(mat, i + 1, toRow, fromCol, toCol, key);
            }
 
            // If middle key is greater then search left vertical
            // matrix and right hand side matrix
            else
            {
                // search left vertical if such matrix exists
                if (j - 1 >= fromCol)
                search(mat, fromRow, toRow, fromCol, j - 1, key);
            }
        }
    }
 
// Driver code
int main()
{
    int mat[ROW][COL] = { {10, 20, 30, 40},
                            {15, 25, 35, 45},
                            {27, 29, 37, 48},
                            {32, 33, 39, 50}};
    int key = 50;
    for (int i = 0; i < ROW; i++)
    for (int j = 0; j < COL; j++)
        search(mat, 0, ROW - 1, 0, COL - 1, mat[i][j]);
    return 0;
}
 
// This code is contributed by Rajput-Ji

// Java program for implementation of divide and conquer algorithm
// to find a given key in a row-wise and column-wise sorted 2D array
class SearchInMatrix
{
    public static void main(String[] args)
    {
        int[][] mat = new int[][] { {10, 20, 30, 40},
                                    {15, 25, 35, 45},
                                    {27, 29, 37, 48},
                                    {32, 33, 39, 50}};
        int rowcount = 4,colCount=4,key=50;
        for (int i=0; i<rowcount; i++)
          for (int j=0; j<colCount; j++)
             search(mat, 0, rowcount-1, 0, colCount-1, mat[i][j]);
    }
 
    // A divide and conquer method to search a given key in mat[]
    // in rows from fromRow to toRow and columns from fromCol to
    // toCol
    public static void search(int[][] mat, int fromRow, int toRow,
                              int fromCol, int toCol, int key)
    {
        // Find middle and compare with middle
        int i = fromRow + (toRow-fromRow )/2;
        int j = fromCol + (toCol-fromCol )/2;
        if (mat[i][j] == key) // If key is present at middle
          System.out.println("Found "+ key + " at "+ i +
                               " " + j);
        else
        {
            // right-up quarter of matrix is searched in all cases.
            // Provided it is different from current call
            if (i!=toRow || j!=fromCol)
             search(mat,fromRow,i,j,toCol,key);
 
            // Special case for iteration with 1*2 matrix
            // mat[i][j] and mat[i][j+1] are only two elements.
            // So just check second element
            if (fromRow == toRow && fromCol + 1 == toCol)
              if (mat[fromRow][toCol] == key)
                System.out.println("Found "+ key+ " at "+
                                   fromRow + " " + toCol);
 
            // If middle key is lesser then search lower horizontal
            // matrix and right hand side matrix
            if (mat[i][j] < key)
            {
                // search lower horizontal if such matrix exists
                if (i+1<=toRow)
                  search(mat, i+1, toRow, fromCol, toCol, key);
            }
 
            // If middle key is greater then search left vertical
            // matrix and right hand side matrix
            else
            {
                // search left vertical if such matrix exists
                if (j-1>=fromCol)
                  search(mat, fromRow, toRow, fromCol, j-1, key);
            }
        }
    }
}

# Python3 program for implementation of
# divide and conquer algorithm to find
# a given key in a row-wise and column-wise
# sorted 2D array a divide and conquer method
# to search a given key in mat in rows from
# fromRow to toRow and columns from fromCol to
# toCol
def search(mat, fromRow, toRow, fromCol, toCol, key):
 
    # Find middle and compare with middle
    i = fromRow + (toRow - fromRow) // 2;
    j = fromCol + (toCol - fromCol) // 2;
    if (mat[i][j] == key): # If key is present at middle
        print("Found " , key , " at " , i , " " , j);
    else:
 
        # right-up quarter of matrix is searched in all cases.
        # Provided it is different from current call
        if (i != toRow or j != fromCol):
            search(mat, fromRow, i, j, toCol, key);
 
        # Special case for iteration with 1*2 matrix
        # mat[i][j] and mat[i][j+1] are only two elements.
        # So just check second element
        if (fromRow == toRow and fromCol + 1 == toCol):
            if (mat[fromRow][toCol] == key):
                print("Found " , key , " at " , fromRow , " " , toCol);
 
        # If middle key is lesser then search lower horizontal
        # matrix and right hand side matrix
        if (mat[i][j] < key):
 
            # search lower horizontal if such matrix exists
            if (i + 1 <= toRow):
                search(mat, i + 1, toRow, fromCol, toCol, key);
 
        # If middle key is greater then search left vertical
        # matrix and right hand side matrix
        else:
             
            # search left vertical if such matrix exists
            if (j - 1 >= fromCol):
                search(mat, fromRow, toRow, fromCol, j - 1, key);
 
# Driver code
if __name__ == '__main__':
    mat = [[ 10, 20, 30, 40],
           [15, 25, 35, 45],
           [27, 29, 37, 48],
           [32, 33, 39, 50]];
    rowcount = 4; colCount = 4; key = 50;
    for i in range(rowcount):
        for j in range(colCount):
            search(mat, 0, rowcount - 1, 0, colCount - 1, mat[i][j]);
 
# This code is contributed by 29AjayKumar

// C# program for implementation of
// divide and conquer algorithm
// to find a given key in a row-wise
// and column-wise sorted 2D array
using System;
 
public class SearchInMatrix
{
    public static void Main(String[] args)
    {
        int[,] mat = new int[,] { {10, 20, 30, 40},
                                    {15, 25, 35, 45},
                                    {27, 29, 37, 48},
                                    {32, 33, 39, 50}};
        int rowcount = 4, colCount = 4, key = 50;
        for (int i = 0; i < rowcount; i++)
            for (int j = 0; j < colCount; j++)
            search(mat, 0, rowcount - 1, 0, colCount - 1, mat[i, j]);
    }
 
    // A divide and conquer method to
    // search a given key in mat[]
    // in rows from fromRow to toRow
    // and columns from fromCol to
    // toCol
    public static void search(int[,] mat, int fromRow, int toRow,
                            int fromCol, int toCol, int key)
    {
        // Find middle and compare with middle
        int i = fromRow + (toRow-fromRow )/2;
        int j = fromCol + (toCol-fromCol )/2;
        if (mat[i, j] == key) // If key is present at middle
        Console.WriteLine("Found "+ key + " at "+ i +
                            " " + j);
        else
        {
            // right-up quarter of matrix is searched in all cases.
            // Provided it is different from current call
            if (i != toRow || j != fromCol)
            search(mat, fromRow, i, j, toCol, key);
 
            // Special case for iteration with 1*2 matrix
            // mat[i][j] and mat[i][j+1] are only two elements.
            // So just check second element
            if (fromRow == toRow && fromCol + 1 == toCol)
            if (mat[fromRow,toCol] == key)
                Console.WriteLine("Found "+ key + " at "+
                                fromRow + " " + toCol);
 
            // If middle key is lesser then search lower horizontal
            // matrix and right hand side matrix
            if (mat[i, j] < key)
            {
                // search lower horizontal if such matrix exists
                if (i + 1 <= toRow)
                search(mat, i + 1, toRow, fromCol, toCol, key);
            }
 
            // If middle key is greater then search left vertical
            // matrix and right hand side matrix
            else
            {
                // search left vertical if such matrix exists
                if (j - 1 >= fromCol)
                search(mat, fromRow, toRow, fromCol, j - 1, key);
            }
        }
    }
}
 
// This code has been contributed by 29AjayKumar

<script>
 
// JavaScript program for implementation
// of divide and conquer algorithm
// to find a given key in a row-wise
// and column-wise sorted 2D array
     
 
    // A divide and conquer method to search a given key in mat
    // in rows from fromRow to toRow and columns from fromCol to
    // toCol
    function search(mat , fromRow , toRow,
                               fromCol , toCol , key)
    {
        // Find middle and compare with middle
        var i = parseInt(fromRow + (toRow-fromRow )/2);
        var j = parseInt(fromCol + (toCol-fromCol )/2);
        if (mat[i][j] == key) // If key is present at middle
          document.write("Found "+ key + " at "+ i +
                               " " + j+"<br/>");
        else
        {
            // right-up quarter of matrix is searched in all cases.
            // Provided it is different from current call
            if (i!=toRow || j!=fromCol)
             search(mat,fromRow,i,j,toCol,key);
 
            // Special case for iteration with 1*2 matrix
            // mat[i][j] and mat[i][j+1] are only two elements.
            // So just check second element
            if (fromRow == toRow && fromCol + 1 == toCol)
              if (mat[fromRow][toCol] == key)
                document.write("Found "+ key+ " at "+
                                   fromRow + " " + toCol+"<br/>");
 
            // If middle key is lesser then search lower horizontal
            // matrix and right hand side matrix
            if (mat[i][j] < key)
            {
                // search lower horizontal if such matrix exists
                if (i+1<=toRow)
                  search(mat, i+1, toRow, fromCol, toCol, key);
            }
 
            // If middle key is greater then search left vertical
            // matrix and right hand side matrix
            else
            {
                // search left vertical if such matrix exists
                if (j-1>=fromCol)
                  search(mat, fromRow, toRow, fromCol, j-1, key);
            }
        }
        }
 
       var mat = [[10, 20, 30, 40],
                   [15, 25, 35, 45],
                   [27, 29, 37, 48],
                   [32, 33, 39, 50]];
        var rowcount = 4,colCount=4,key=50;
        for (var i=0; i<rowcount; i++)
          for (var j=0; j<colCount; j++)
             search(mat, 0, rowcount-1, 0, colCount-1, mat[i][j]);
              
// This code contributed by umadevi9616
 
</script>

Producción:  

Found 10 at 0 0
Found 20 at 0 1
Found 30 at 0 2
Found 40 at 0 3
Found 15 at 1 0
Found 25 at 1 1
Found 35 at 1 2
Found 45 at 1 3
Found 27 at 2 0
Found 29 at 2 1
Found 37 at 2 2
Found 48 at 2 3
Found 32 at 3 0
Found 33 at 3 1
Found 39 at 3 2
Found 50 at 3 3

Complejidad temporal: 
nos dan una array *n, el algoritmo puede verse como recurrente para 3 arrays de tamaño n/2 xn/2. Lo siguiente es la recurrencia de la complejidad del tiempo 

 T(n) = 3T(n/2) + O(1) 

La solución de recurrencia es O(n ^1.58 ) usando el Método Maestro . 
Pero la implementación real requiere una subarray de tamaño nxn/2 o n/2 xn y otra subarray de tamaño n/2 xn/2.
Este artículo es una contribución de Kaushik Lele . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.