Algoritmo di ricerca binaria o dicotomica in JavaScript

La ricerca binaria, nota anche come ricerca dicotomica, è un efficace algoritmo di ricerca utilizzato per trovare un elemento all'interno di un array ordinato. Questo metodo suddivide ripetutamente l'array a metà e riduce il campo di ricerca finché non trova l'elemento cercato o determina che l'elemento non è presente. Esploriamo in dettaglio il funzionamento e l'implementazione della ricerca binaria in JavaScript.

L'algoritmo di ricerca binaria opera sui seguenti principi:

1. Array ordinato: l'array su cui si applica la ricerca binaria deve essere ordinato in modo ascendente o discendente.

2. Divide et impera: l'algoritmo divide continuamente l'array a metà per restringere il campo di ricerca.

3. Confronto con l'elemento medio: si confronta l'elemento medio dell'array con l'elemento cercato.

4. Ricerca continua: se l'elemento cercato è maggiore dell'elemento medio, la ricerca continua nella metà superiore dell'array; se è minore, nella metà inferiore.

5. Ripetizione del processo: si ripete il processo finché l'elemento è trovato o la porzione dell'array è ridotta a zero.

Implementazione della ricerca binaria in JavaScript

Ecco un'implementazione di base della ricerca binaria in JavaScript:

function ricercaBinaria(arr, elementoCercato) {
  let inizio = 0;
  let fine = arr.length - 1;

  while (inizio <= fine) {
    let medio = Math.floor((inizio + fine) / 2);
    let elementoMedio = arr[medio];

    if (elementoMedio === elementoCercato) {
      return medio; // Restituisce l'indice dell'elemento trovato
    } else if (elementoMedio < elementoCercato) {
      inizio = medio + 1; // Continua la ricerca nella metà superiore
    } else {
      fine = medio - 1; // Continua la ricerca nella metà inferiore
    }
  }

  return -1; // Restituisce -1 se l'elemento non è presente nell'array
}

Questa funzione ricercaBinaria accetta un array ordinato e l'elemento da cercare come argomenti e restituisce l'indice dell'elemento cercato nell'array. Se l'elemento non viene trovato, viene restituito il valore -1.

let array = [11, 12, 22, 25, 34, 64, 90];
let elemento = 22;
console.log(ricercaBinaria(array, elemento)); // Output: 2 (indice dell'elemento cercato)

Complessità temporale della ricerca binaria

La ricerca binaria ha una complessità temporale di O(log n), dove "n" rappresenta la lunghezza dell'array. Questo la rende notevolmente efficiente rispetto alla ricerca sequenziale su dataset ordinati.

La ricerca binaria è estremamente efficiente su array ordinati e spesso utilizzata in applicazioni in cui è necessario cercare rapidamente in grandi dataset ordinati, come ad esempio nelle basi di dati o nell'analisi di algoritmi di ordinamento.