Búsqueda Binaria en C#

Búsqueda Binaria en C#

El algoritmo de búsqueda binaria es un excelente método para buscar datos dentro de una estructura(generalmente un arreglo unidimensional). Se le da el nombre de búsqueda binaria por que el algoritmo divide en dos el arreglo, aludiendo al concepto de bit, el cual puede tener dos estados.

La única condición para usar este algoritmo es que los datos dentro del arreglo estén ordenados de menor a mayor.

La solución mas fácil para realizar una búsqueda es por fuerza bruta, pero este método puede resultar bastante ineficiente cuando se tiene una gran cantidad de datos, ya que habría que buscar posición por posición hasta encontrar el dato que queremos.

El código por fuerza bruta es bastante sencillo:

             for(int i=0; i<Arreglo.length; i++)

                     if(Arreglo[i] == elemento)

                     System.out.println("\nElemento encontrado en la posicion: " + i);

Solo se recorre todo el arreglo y verificamos si la posición i es igual al dato que queremos buscar, el código anterior se puede mejorar simplemente agregándole una bandera, pero aun así no es lo suficientemente bueno.

El algoritmo de búsqueda binaria es el siguiente:

1. Se declaran los índices superior e inferior. El inferior en 0 y el superior con el tamaño del arreglo menos 1.
2. Se calcula el centro del arreglo con la siguiente formula:  centro = (superior + inferior) / 2
3. Verificamos si el arreglo en la posición centro es igual al dato que buscamos. Si es igual significa que encontramos el dato y retornamos centro.
4. Si son diferentes verificamos si el arreglo en la posición centro es mayor al dato que queremos buscar. Si es mayor actualizamos superior: superior = centro - 1, si no actualizamos inferior: inferior = centro + 1.

 5. Volvemos al paso 2.

Si cuando ya no se cumpla la condición del ciclo y no se encontró el dato retornamos -1

indicando que el dato no se encuentra en el arreglo.

Búsqueda Binaria en C# 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace BusquedaBinaria

{

    class Busqueda

    {

        private int[] vector;

        public void Cargar()

        {

            Console.WriteLine("Busqueda Binaria");

            Console.WriteLine("Ingrese 10 Elementos");

            string linea;

            vector = new int[10];

            for (int f = 0; f< vector.Length; f++)

            {

                Console.Write("Ingrese elemento " + (f + 1) + ": ");

                linea = Console.ReadLine();

                vector[f] = int.Parse(linea);

            }

        }

        public void busqueda(int num)

        {

            int l = 0, h = 9;

            int m = 0;

            bool found = false;

            while (l <= h && found == false)

            {

                m = (l + h) / 2;

                if (vector[m] == num)

                    found = true;

                if (vector[m] > num)

                    h = m - 1;

                else

                    l = m + 1;

            }

            if (found == false)

            { Console.Write("\nEl elemento {0} no esta en el arreglo", num); }

            else

            { Console.Write("\nEl elemento {0} esta en la posicion: {1}", num, m + 1); }

        }

        public void Imprimir()

        {

            for (int f = 0; f< vector.Length; f++)

            {

                Console.Write(vector[f] + "  ");

            }

        }

        static void Main(string[] args)

        {

            Busqueda pv = new Busqueda();

            pv.Cargar();

            pv.Imprimir();

            Console.Write("\n\nElemento a buscar: ");

            int num = int.Parse(Console.ReadLine());

            pv.busqueda(num);

            Console.ReadKey();

           

        }

    }

}

Al ejecutar el código muestra el siguiente resultado

Método de Ordenamiento Merge Sort en C#

Método de Ordenamiento Merge Sort en C#

Esta vez estaremos hablando de Ordenación por Mezcla (Merge Sort), otro algoritmo recursivo bastante eficiente para ordenar un array, que tiene un orden de complejidad O(nlogn) al igual que Quick Sort. Fue desarrollado en 1945 por John Von Neumann según wikipedia.

Estrategia de Merge Sort

Merge Sort está basado en la técnica de diseño de algoritmos Divide y Vencerás, de la cual se habló aquí mismo hace un tiempo. Recordando un poco, esta técnica consiste en dividir el problema a resolver en sub problemas del mismo tipo que a su vez se dividirán, mientras no sean suficientemente  pequeños o triviales.

Veamos una panorámica de la estrategia que sigue este algoritmo para ordenar una secuencia S de n elementos:

• Si S tiene uno o ningún elemento, está ordenada
• Si S tiene al menos dos elementos se divide en dos secuencias S1 y S2
• S1 contiene los primeros n/2 elementos y S2 los restantes
• Ordenar S1 y S2, aplicando recursivamente este procedimiento
• Mezclar S1 y S2 en S, de forma que ya S1 y S2 estén ordenados
• Veamos ahora como sería la estrategia para mezclar las secuencias:

Se tienen referencias al principio de cada una de las secuencias a mezclar (S1 y S2). Mientras en alguna secuencia queden elementos, se inserta en la secuencia resultante (S) el menor de los elementos referenciados y se avanza esa referencia una posición.

Pseudocódigo del Método de Ordenamiento Merge Sort

Como ven, la idea es bastante simple, pero programarla no tanto. Para no dar de golpe la solución, veamos primero un pseudocódigo del algoritmo:

  function mergesort(array A[x..y])

  begin

    if (x-y > 1)):

      array A1 := mergesort(A[x..(int( x+y / 2))])

      array A2 := mergesort(A[int(1+(x+y / 2))..y])

      return merge(A1, A2)

    else:

      return A

  end

  function merge(array A1[0..n1], array A2[0..n2])

  begin

    integer p1 := 0

    integer p2 := 0

    array R[0..(n1 + n2 + 2)]//suponiendo que n1 y n2 son las posiciones

    //del array y no el length de este mismo, de otro modo seria (n1 + n2)

    while (p1 <= n1 or p2 <= n2):

      if (p1 <= n1 and A1[p1] <= A2[p2]):

         R[p1 + p2] := A1[p1]

         p1 := p1 + 1

      else

         if (p2 <= n2 and A1[p1] > A2[p2]):

           R[p1 + p2] := A2[p2]

           p2 := p2 + 1

    return R

  end

Ejemplo del Método de Ordenamiento Merge Sort en C# 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace MergeSort

{

    class Program

    {

        static void Main(string[] args)

        {

            int[] nums = new int[40];

            Console.WriteLine("Metodo de Merge Sort");

            Console.Write("Cuantos longitud del vector: ");

            string linea;

            linea = Console.ReadLine();

            int cant;

            cant = int.Parse(linea);

            nums = new int[cant];

            for (int f = 0; f < nums.Length; f++)

            {

                Console.Write("Ingrese elemento " + (f + 1) + ": ");

                linea = Console.ReadLine();

                nums[f] = int.Parse(linea);

            }

            MergeSort(nums);

            Console.WriteLine("Vector Ordenado Ascendentemente");

            for (int i = 0; i < nums.Length; i++)

                Console.Write(nums[i] + " ");

            Console.ReadLine();

        }

        //Método portal que llama al método recursivo inicial

        public static void MergeSort(int[] x)

        {

            MergeSort(x, 0, x.Length - 1);

        }

        static private void MergeSort(int[] x, int desde, int hasta)

        {

            //Condicion de parada

            if (desde == hasta)

                return;

            //Calculo la mitad del array

            int mitad = (desde + hasta) / 2;

            //Voy a ordenar recursivamente la primera mitad

            //y luego la segunda

            MergeSort(x, desde, mitad);

            MergeSort(x, mitad + 1, hasta);

            //Mezclo las dos mitades ordenadas

            int[] aux = Merge(x, desde, mitad, mitad + 1, hasta);

            Array.Copy(aux, 0, x, desde, aux.Length);

        }

        //Método que mezcla las dos mitades ordenadas

        static private int[] Merge(int[] x, int desde1, int hasta1, int desde2, int hasta2)

        {

            int a = desde1;

            int b = desde2;

            int[] result = new int[hasta1 - desde1 + hasta2 - desde2 + 2];

            for (int i = 0; i < result.Length; i++)

            {

                if (b != x.Length)

                {

                    if (a > hasta1 && b <= hasta2)

                    {

                        result[i] = x[b];

                        b++;

                    }

                    if (b > hasta2&& a <= hasta1)

                    {

                        result[i] = x[a];

                        a++;

                    }

                    if (a <= hasta1&& b <= hasta2)

                    {

                        if (x[b] <= x[a])

                        {

                            result[i] = x[b];

                            b++;

                        }

                        else

                        {

                            result[i] = x[a];

                            a++;

                        }

                    }

                }

                else

                {

                    if (a <= hasta1)

                    {

                        result[i] = x[a];

                        a++;

                    }

                }

            }

            return result;

        }

    }

}

Al ejecutar el código muestra el siguiente resultado

Ejemplo de Vectores y Matrices en C#

Ejemplo de Vectores y Matrices en C#

Se desea saber la temperatura media trimestral de cuatro provincias. Para ello se tiene como dato las temperaturas medias mensuales de dichas provincias.

Se debe ingresar el nombre de la provincia y seguidamente las tres temperaturas medias mensuales.

Seleccionar las estructuras de datos adecuadas para el almacenamiento de los datos en memoria.

1. Ingresar por teclado los nombres de las provincias y las temperaturas medias mensuales.
2. Imprimir los nombres de las provincias y las temperaturas medias mensuales de las mismas.
3. Calcular la temperatura media trimestral de cada provincia.
4. Imprimir los nombres de las provincias y las temperaturas medias trimestrales.
5. Imprimir el nombre de la provincia con la temperatura media trimestral mayor.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Matriz

{

    class Matriz

    {

        private string[] paises;

        private int[,] tempmen;

        private int[] temptri;

        public void Cargar()

        {

            paises = new String[4];

            tempmen = new int[4, 3];

            for (int f = 0; f< paises.Length; f++)

            {

                Console.Write("Ingrese el nombre de la provincia "+(f+1)+": ");

                paises[f] = Console.ReadLine();

                for (int c = 0; c < tempmen.GetLength(1); c++)

                {

                    Console.Write("Ingrese temperatura mensual " + (c + 1) + ": ");

                    string linea = Console.ReadLine();

                    tempmen[f, c] = int.Parse(linea);

                }

            }

        }

        public void ImprimirTempMensuales()

        {

            for (int f = 0; f< paises.Length; f++)

            {

                Console.Write("Provincia:" + paises[f] + ":");

                for (int c = 0; c < tempmen.GetLength(1); c++)

                {

                    Console.Write(tempmen[f, c] + " ");

                }

                Console.WriteLine();

            }

        }

        public void CalcularTemperaturaTri()

        {

            temptri = new int[4];

            for (int f = 0; f< tempmen.GetLength(0); f++)

            {

                int suma = 0;

                for (int c = 0; c < tempmen.GetLength(1); c++)

                {

                    suma = suma + tempmen[f, c];

                }

                temptri[f] = suma / 3;

            }

        }

        public void ImprimirTempTrimestrales()

        {

            Console.WriteLine("Temperaturas trimestrales.");

            for (int f = 0; f< paises.Length; f++)

            {

                Console.WriteLine(paises[f] + " " + temptri[f]);

            }

        }

        public void PaisMayorTemperaturaTri()

        {

            int may = temptri[0];

            string nom = paises[0];

            for (int f = 0; f< paises.Length; f++)

            {

                if (temptri[f] > may)

                {

                    may = temptri[f];

                    nom = paises[f];

                }

            }

            Console.WriteLine("Provincia con temperatura trimestral mayor es " + nom + " que tiene una temperatura de " + may);

        }

        static void Main(string[] args)

        {

            Matriz ma = new Matriz();

            ma.Cargar();

            ma.ImprimirTempMensuales();

            ma.CalcularTemperaturaTri();

            ma.ImprimirTempTrimestrales();

            ma.PaisMayorTemperaturaTri();

            Console.ReadKey();

        }

    }

}

Al ejecutar el código muestra el siguiente resultado

Suma de Matrices en C#

Suma de Matrices en C#

Realizar un programa que permita la suma de dos matrices de 3x3 y el resultado almacenar en un tercer matriz 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace PruebaVector

{

    class PruebaVector

    {

        private int[,] MatrizA;

        private int[,] MatrizB;

        private int[,] MatrizC;

        public void Cargar()

        {

            MatrizA = new int[10,10];

            MatrizB = new int[10, 10];

            MatrizC = new int[10, 10];

            Console.WriteLine("Ingresando datos al matriz A");

            for (int i = 1; i<= 3; i++)

            {

                for (int j = 1; j <= 3; j++)

                {

                    Console.Write("Ingrese posicion [" + i + "," + j + "]: ");

                    string linea;

                    linea = Console.ReadLine();

                    MatrizA[i, j] = int.Parse(linea);

                }

            }

            Console.WriteLine("Ingresando datos al matriz B");

            for (int i = 1; i <= 3; i++)

            {

                for (int j = 1; j <= 3; j++)

                {

                    Console.Write("Ingrese posicion [" + i + "," + j + "]: ");

                    string linea;

                    linea = Console.ReadLine();

                    MatrizB[i, j] = int.Parse(linea);

                }

            }

            //Sumamos la matrizA y la MatrizB

            for (int i = 1; i< = 3; i++)

            {

                for (int j = 1; j <= 3; j++)

                {

                    MatrizC[i,j]=MatrizA[i,j]+MatrizB[i,j];

                }

            }

        }

        // visualizamos la suma de las matrices

        public void visualizar()

        {

            Console.WriteLine("La suma de la MatrizA y MatrizB es :");

            for (int i = 1; i< = 3; i++)

            {

                Console.Write("\n");

                for (int j = 1; j <= 3; j++)

                {

                    Console.Write(MatrizC[i,j]+"  ");

                }

            }

            Console.ReadKey();

        }

        static void Main(string[] args)

        {

            PruebaVector pv = new PruebaVector();

            pv.Cargar();

            pv.visualizar();

        }

    }

}

Al ejecutar el código muestra el siguiente resultado