Ricerca binaria in C#

La ricerca binaria è un algoritmo che viene usato per trovare gli elementi in un array ordinato; il fatto che sia ordinato è fondamentale e obbligatorio.

Questo algoritmo è più efficiente della ricerca sequenziale, in quanto usa la logica del divide et impera.

In sostanza si procede suddividendo l'array man mano che la ricerca non trova l'elemento, andando a ricercarlo solo in una parte dell'array, che diventa sempre più piccolo.

Quindi, partendo da un elemento casuale:

• se la chiave è uguale, abbiamo trovato l'elemento
• se la chiave è maggiore si prosegue cercando verso destra
• se la chiave è minore si prosegue cercando verso sinistra

Ecco perchè l'array deve essere ordinato.

Detto ciò, vediamo un esempio in C#:

using System;

namespace CSharpTest
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = { 20, 32, 51, 106, 400 };
            int n = arr.Length;
            int x = 106;

            int result = binarySearch(arr, 0, n - 1, x);

            if (result == -1)
            {
                Console.WriteLine("Elemento non trovato");
            }
            else
            {
                Console.WriteLine("Elemento trovato; Indice " + result);
            }

            Console.ReadLine();
        }

        static int binarySearch(int[] arr, int sx, int rx, int x)
        {
            if (rx >= sx)
            {
                int mid = sx + (rx - sx) / 2;

                if (arr[mid] == x)
                {
                    return mid;
                }

                if (arr[mid] > x)
                {
                    return binarySearch(arr, sx, mid - 1, x);
                }

                return binarySearch(arr, mid + 1, rx, x);
            }

            return -1;
        }
    }
}

Enjoy!