Recherche dans un tableau 2D trié par ligne et par colonne à l’aide de l’algorithme Divide and Conquer

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]);

    }

    

    

    

    

    

    public static void search(int[,] mat, int fromRow, int toRow,

                            int fromCol, int toCol, int key)

    {

        

        int i = fromRow + (toRow-fromRow )/2;

        int j = fromCol + (toCol-fromCol )/2;

        if (mat[i, j] == key)

        Console.WriteLine("Found "+ key + " at "+ i +

                            " " + j);

        else

        {

            

            

            if (i != toRow || j != fromCol)

            search(mat, fromRow, i, j, toCol, key);

            

            

            

            if (fromRow == toRow && fromCol + 1 == toCol)

            if (mat[fromRow,toCol] == key)

                Console.WriteLine("Found "+ key + " at "+

                                fromRow + " " + toCol);

            

            

            if (mat[i, j] < key)

            {

                

                if (i + 1 <= toRow)

                search(mat, i + 1, toRow, fromCol, toCol, key);

            }

            

            

            else

            {

                

                if (j - 1 >= fromCol)

                search(mat, fromRow, toRow, fromCol, j - 1, key);

            }

        }

    }

}

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Aller en haut