Confronto tra ricerca lineare e ricerca binaria

4.1 Confronto della complessità temporale tra ricerca lineare e binaria

Confrontiamo la complessità temporale della ricerca lineare e binaria.

Ricerca lineare:

• Complessità temporale: O(n), dove n è il numero di elementi nell'array o nella lista.
• Miglior caso: O(1) — elemento trovato al primo posto.
• Casomedio: O(n/2) = O(n) — elemento trovato in media da qualche parte a metà.
• Peggior caso: O(n) — elemento trovato all'ultimo posto o assente.

Ricerca binaria:

• Complessità temporale: O(log n), dove n è il numero di elementi nell'array o nella lista.
• Miglior caso: O(1) — elemento trovato al primo passo (elemento centrale).
• Casomedio: O(log n) — ricerca in un array ordinato.
• Peggior caso: O(log n) — elemento trovato all'ultimo passo o assente.

Esempio di analisi della complessità temporale

Ricerca lineare:

• Array [1, 3, 5, 7, 9, 11, 13], elemento cercato 7.
• Controllo di ogni elemento fino a trovare 7 all'indice 3.
• Occorrono 4 controlli, che corrispondono a O(n).

Ricerca binaria:

• Array [1, 3, 5, 7, 9, 11, 13], elemento cercato 7.
• Elemento centrale (7) trovato al primo passo.
• Occorre 1 controllo, che corrisponde a O(log n).

4.2 Vantaggi e svantaggi di ciascun metodo

Vediamo i vantaggi e gli svantaggi di ciascun tipo di ricerca.

Ricerca lineare:

Vantaggi:

• Semplicità di implementazione: La ricerca lineare è molto facile da implementare e capire.
• Nessun requisito per i dati: La ricerca lineare può essere applicata a dati non ordinati.
• Adatta a piccoli array: La ricerca lineare è efficace per array di piccole dimensioni.

Svantaggi:

• Bassa efficienza per grandi array: La complessità temporale O(n) lo rende inefficace per grandi array.
• Tempo di esecuzione lungo: Per grandi array, la ricerca lineare può richiedere molto tempo, soprattutto se l'elemento cercato è vicino alla fine dell'array o assente.

Ricerca binaria:

Vantaggi:

• Alta efficienza per grandi array: La complessità temporale O(log n) lo rende molto efficiente per grandi array.
• Esplorazione veloce: La ricerca binaria è significativamente più veloce della ricerca lineare quando si lavora con grandi array ordinati.

Svantaggi:

• Richiede dati ordinati: La ricerca binaria funziona solo con array ordinati, il che può richiedere tempo aggiuntivo per la pre-ordinazione.
• Complessità di implementazione: L'implementazione della ricerca binaria è più complessa rispetto alla ricerca lineare.

4.3 Quando utilizzare quale ricerca

Vediamo quando usare la ricerca lineare e quando la ricerca binaria.

Ricerca lineare.

Usa la ricerca lineare quando:

• L'array o la lista non sono ordinati.
• La dimensione dell'array o della lista è piccola.
• Serve semplicità e una soluzione veloce senza costi aggiuntivi di ordinamento.
• È necessario trovare la prima occorrenza o tutte le occorrenze di un elemento.
• I dati arrivano in tempo reale e la loro pre-ordinazione non è possibile o non è conveniente.

Ricerca binaria.

Usa la ricerca binaria se:

• L'array o la lista sono ordinati.
• La dimensione dell'array o della lista è grande.
• C'è una ricerca frequente di elementi nello stesso insieme di dati (puoi preordinare i dati una volta).
• È importante avere un'alta velocità di ricerca.
• È accettabile spendere tempo per la pre-ordinazione dei dati.

4.4 Esempi di problemi per la ricerca lineare

1. Ricerca in una lista non ordinata

Bisogna trovare l'indice di un dato numero in una lista di numeri non ordinata.

Esempio:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

arr = [4, 2, 7, 1, 9, 3]
target = 7
print(linear_search(arr, target))  # Output: 2

2. Ricerca della prima occorrenza in un array

Bisogna trovare la prima occorrenza di un dato elemento in una lista di stringhe.

Esempio:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

words = ["apple", "banana", "cherry", "date", "banana"]
target = "banana"
print(linear_search(words, target))  # Output: 1

3. Ricerca nei dati in tempo reale

Trovare un elemento in un flusso di dati che arrivano in tempo reale.

Esempio:

import random

def find_in_stream(stream, target):
    for index, element in enumerate(stream):
        if element == target:
            return index
    return -1

stream = [random.randint(1, 100) for _ in range(100)]
target = 50
print(find_in_stream(stream, target))

4.5 Esempi di problemi per la ricerca binaria

1. Ricerca in un array ordinato

Bisogna trovare l'indice di un dato numero in un array ordinato di numeri.

Esempio:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target))  # Output: 3

2. Ricerca frequente in un grande set di dati

Cercare frequentemente elementi in un grande array ordinato di numeri.

Esempio:

import random

sorted_large_array = sorted([random.randint(1, 1000000) for _ in range(1000000)])
target = random.choice(sorted_large_array)
print(binary_search(sorted_large_array, target))

3. Ricerca di un elemento in un database ordinato

Trovare una registrazione in un database ordinato per il campo chiave.

Esempio:

database = sorted([{"id": i, "value": f"record_{i}"} for i in range(100000)])
def binary_search_db(db, target_id):
    left, right = 0, len(db) - 1
    while left <= right:
        mid = (left + right) // 2
        if db[mid]["id"] == target_id:
            return db[mid]
        elif db[mid]["id"] < target_id:
            left = mid + 1
        else:
            right = mid - 1
    return None

target_id = 54321
print(binary_search_db(database, target_id))

1

Опрос

Algoritmi di ricerca,  53 уровень,  3 лекция

недоступен

Algoritmi di ricerca

Algoritmi di ricerca

Открыть