Ricerca lineare e binaria

Problema: data una sequenza v e un valore x, trovare un indice i con v[i] == x, o segnalare che non c'è (convenzione: restituire -1).

Ricerca lineare

Definizione (ricerca lineare). Funziona su qualunque sequenza, anche non ordinata.

def ricerca_lineare(v, x):
    for i in range(len(v)):
        if v[i] == x:
            return i
    return -1

• Caso migliore $O(1)$, caso peggiore $O(n)$ (elemento assente).
• Restituisce la prima occorrenza.
• È ciò che fanno x in v e v.index(x).

Esempio. ricerca_lineare([4, 7, 7, 1], 7) restituisce 1 (la prima occorrenza) e ricerca_lineare([4, 7], 5) restituisce -1.

Ricerca binaria

Definizione (ricerca binaria). Richiede v ordinata. Si confronta x con l'elemento centrale e si scarta metà dell'intervallo a ogni passo.

def ricerca_binaria(v, x):
    lo, hi = 0, len(v) - 1          # intervallo di ricerca [lo, hi], estremi inclusi
    while lo <= hi:
        m = (lo + hi) // 2
        if v[m] == x:
            return m
        elif v[m] < x:
            lo = m + 1              # x, se c'è, sta a destra di m
        else:
            hi = m - 1              # x, se c'è, sta a sinistra di m
    return -1

Invariante: se x è in v, allora si trova in v[lo..hi]. Il ciclo termina perché a ogni giro l'intervallo si riduce di almeno un elemento (m + 1, m - 1); quando lo > hi l'intervallo è vuoto e x non c'è.

Costo: dopo $k$ iterazioni restano circa $n / 2^k$ elementi, quindi al più $\lfloor \log_2 n \rfloor + 1$ iterazioni: $O(\log n)$. Con $n = 10^6$ bastano 20 confronti.

Esempio. ricerca_binaria([2, 5, 8, 12, 16, 23, 38], 23) restituisce 5; con $n=10^6$ bastano al più $\lfloor\log_210^6\rfloor+1=20$ iterazioni.

Esempio su v = [2, 5, 8, 12, 16, 23, 38], x = 23:

Versione ricorsiva

def ricerca_binaria_ric(v, x, lo=0, hi=None):
    if hi is None:
        hi = len(v) - 1
    if lo > hi:
        return -1
    m = (lo + hi) // 2
    if v[m] == x:
        return m
    if v[m] < x:
        return ricerca_binaria_ric(v, x, m + 1, hi)
    return ricerca_binaria_ric(v, x, lo, m - 1)

Equazione del costo $T(n) = T(n/2) + O(1)$ (vedi RicorsioneFunzioni che chiamano se stesse: caso base e passo ricorsivo, stack delle chiamate, esempi su numeri, stringhe e liste, ricorsione multipla e suo costo, divide et impera, confronto con l'iterazione.Ricorsione →, Complessità computazionaleCosto di un algoritmo in funzione della dimensione dell'input; caso peggiore, migliore e medio; notazione O-grande e classi di crescita; come contare i passi di cicli e ricorsioni; costo delle operazioni Python.Complessità computazionale →). Passare gli indici e non v[:m]: lo slicing costerebbe $O(n)$ a ogni chiamata.

Quale usare

• Una sola ricerca su dati non ordinati: lineare ($O(n)$); ordinare costa già $O(n \log n)$.
• Molte ricerche sugli stessi dati: ordinare una volta (Algoritmi di ordinamentoSelection sort, insertion sort e bubble sort (quadratici), merge sort (n log n, divide et impera); stabilità, ordinamento sul posto, costo nei vari casi; sort e sorted con key.Algoritmi di ordinamento →) e poi ricerca binaria. Oppure un insieme o dizionario (Dizionari e insiemi in PythonADT mappa e insieme; dict con chiavi hashable, accesso, get, iterazione, conteggi e raggruppamenti; set e operazioni insiemistiche; tabelle hash e costo O(1) medio; Counter e defaultdict.Dizionari e insiemi in Python →), $O(1)$ in media, se non serve l'ordine.

Modulo bisect

Definizione (modulo bisect)

import bisect
v = [2, 5, 8, 8, 12]
bisect.bisect_left(v, 8)     # 2: primo indice dove inserire 8 mantenendo l'ordine
bisect.bisect_right(v, 8)    # 4
bisect.insort(v, 7)          # inserimento ordinato: [2, 5, 7, 8, 8, 12]

bisect_left(v, x) restituisce un indice i con v[i] == x se x c'è (e i < len(v)).

Esempio. Con v = [2, 5, 8, 8, 12], bisect_left(v, 8) restituisce 2 e bisect_right(v, 8) restituisce 4.

Errori tipici

• Ricerca binaria su una lista non ordinata: risultati sbagliati senza errori.
• while lo < hi con estremi inclusi: l'ultimo elemento candidato non viene controllato.
• lo = m o hi = m invece di m + 1 / m - 1: ciclo infinito quando l'intervallo ha due elementi.
• return dentro il ciclo lineare nel ramo else (si esce dopo il primo confronto).