Ricerca binaria

1. Algoritmo di ricerca binaria
2. Esempio di ricerca binaria
3. Implementazione dell’algoritmo di ricerca binaria
4. Complessità dell’algoritmo di ricerca binaria

La ricerca binaria è l’algoritmo di ricerca più popolare ed efficiente. In effetti, è l’algoritmo di ricerca più veloce. Proprio come l’ordinamento a salti, richiede anche l’ordinamento dell’array. Si basa sull’approccio divide et impera in cui dividiamo la matrice in due metà e quindi confrontiamo l’elemento che stiamo cercando con l’elemento centrale. Se l’elemento centrale corrisponde, restituiamo l’indice dell’elemento centrale; in caso contrario, ci spostiamo nella metà sinistra e destra a seconda del valore dell’elemento.

Algoritmo di ricerca binaria

Supponiamo di avere un array non ordinato A[] contenente n elementi e di voler trovare un elemento X.

Esempio di ricerca binaria

Supponiamo di avere l’array: (1, 2, 3, 4, 5, 6, 7, 8, 9) e di voler trovare X - 8.

Implementazione dell’algoritmo di ricerca binaria

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int arr[], int lo, int hi, int x) {
  while (lo <= hi) {
    int m = lo + (hi - lo) / 2;
    if (arr[m] == x) return m;
    if (arr[m] < x)
      lo = m + 1;
    else
      hi = m - 1;
  }
  return -1;
}

int main(void) {
  int n = 9;
  int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  int x = 8;
  int result = binarySearch(arr, 0, n - 1, x);
  if (result == -1) {
    cout << "Element not found !!";
  } else
    cout << "Element found at index " << result;
  return 0;
}

Complessità dell’algoritmo di ricerca binaria

Complessità temporale

• Case nella media

Quando eseguiamo la ricerca binaria, cerchiamo in una metà e scartiamo l’altra metà, riducendo la dimensione dell’array della metà ogni volta.

L’espressione per complessità temporale è data dalla ricorrenza.

T(n) = T(n/2) + k , k is a constant.

Questo risultato di questa ricorrenza dà logn, e la complessità temporale è dell’ordine di O(logn). È più veloce sia della ricerca lineare che della ricerca per salto.

• Caso migliore

Il caso migliore si verifica quando l’elemento centrale è l’elemento che stiamo cercando e viene restituito nella prima iterazione. La complessità temporale nel migliore dei casi è O(1).

• Nel peggiore dei casi

La complessità temporale del caso peggiore è la stessa della complessità temporale del caso medio. La complessità temporale nel caso peggiore è O(logn).

Complessità spaziale

La complessità dello spazio di questo algoritmo è O(1) nel caso di implementazione iterativa perché non richiede alcuna struttura dati diversa dalle variabili temporanee.

Nel caso di implementazione ricorsiva, la complessità dello spazio è O(logn) a causa dello spazio richiesto dallo stack di chiamate ricorsive.