Vai al contenuto

Esercizi · Ricerca lineare e binaria

Esercizi · Capitolo 4 · ogni soluzione si apre con un clic · Capitolo 4: Ricerca lineare e binaria · Eserciziario, volume 1 (PDF)

Negli esercizi di questo capitolo le ricerche sono svolte con i due algoritmi del capitolo «Ricerca lineare e ricerca binaria», richiamati di seguito. Gli indici degli array vanno da \(1\) a \(n\), e viene restituito il valore \(-1\) quando il valore cercato \(m\) non è nell'array.

Algoritmo: LinearSearch

Input: Un array \(a[1..n]\) di \(n\) numeri naturali e un valore \(m\) da cercare
Output: Indice di \(m\) in \(a\), oppure \(-1\) se non trovato
1function LinearSearch(a, n, m)
2\(i := 1\)
3while \(i \le n\) do
4if \(a[i] = m\) then
5return \(i\)// Elemento trovato all'indice \(i\)
6end
7\(i \leftarrow i + 1\)
8end
9return \(-1\)// Elemento non trovato
10end

Algoritmo: BinarySearch

Input: Un array \(a[1..n]\) di \(n\) numeri naturali ordinato in modo non decrescente e un valore \(m\) da cercare
Output: Indice di \(m\) in \(a\), oppure \(-1\) se non trovato
1function BinarySearch(a, n, m)
2\(left\) := \(1\)
3\(right\) := \(n\)
4while \(left \le right\) do
5\(mid\) := \(left + \lfloor (right - left) / 2 \rfloor\)
6if \(a[mid] = m\) then
7return \(mid\)// Elemento trovato
8end
9if \(a[mid] < m\) then
10\(left\) \(\leftarrow\) \(mid + 1\)// Cerca nella metà destra
11end
12else
13\(right\) \(\leftarrow\) \(mid - 1\)// Cerca nella metà sinistra
14end
15end
16return \(-1\)// Elemento non trovato
17end

Esercizio 4.1: Ricerca lineare e ricerca binaria (E1)

Consideriamo il seguente array:

\[ a = [7, 2, 14, 3, 8, 11, 5, 9] \]

con \(n = 8\).

Domande

  1. Applicare l'algoritmo di ricerca lineare (Linear Search) all'array \(a\) per ciascuno dei seguenti valori cercati:

    1. \(m = 11\)

    2. \(m = 7\)

    3. \(m = 9\)

    4. \(m = 4\)

    5. \(m = 14\)

    Per ogni ricerca, mostrare l'esecuzione passo per passo, indicando a ogni iterazione i valori di \(i\), \(a[i]\) e il risultato del confronto, e dare il valore restituito dall'algoritmo.

Soluzione

  1. Ricerca di \(m = 11\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 7 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 2 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 14 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(4\) 4 3 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(5\) 5 8 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(6\) 6 11 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 11 si trova all'indice 6.

  2. Ricerca di \(m = 7\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 7 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 7 si trova all'indice 1.

  3. Ricerca di \(m = 9\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 7 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 2 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 14 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(4\) 4 3 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(5\) 5 8 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(6\) 6 11 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(7\) 7 5 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(8\) 8 9 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 9 si trova all'indice 8.

  4. Ricerca di \(m = 4\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 7 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 2 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 14 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(4\) 4 3 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(5\) 5 8 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(6\) 6 11 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(7\) 7 5 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(8\) 8 9 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(-\) 9 \(-\) \(i > n\) \(\Rightarrow\) il ciclo termina, non trovato!

    Quindi, l'elemento 4 non è presente nell'array (restituisce \(-1\)).

  5. Ricerca di \(m = 14\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 7 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 2 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 14 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 14 si trova all'indice 3.

Esercizio 4.2: Ricerca lineare e ricerca binaria (E2)

Consideriamo il seguente array:

\[ a = [15, 4, 22, 8, 1, 30, 17] \]

con \(n = 7\).

Domande

  1. Applicare l'algoritmo di ricerca lineare (Linear Search) all'array \(a\) per ciascuno dei seguenti valori cercati:

    1. \(m = 22\)

    2. \(m = 15\)

    3. \(m = 17\)

    4. \(m = 10\)

    5. \(m = 1\)

    Per ogni ricerca, mostrare l'esecuzione passo per passo, indicando a ogni iterazione i valori di \(i\), \(a[i]\) e il risultato del confronto, e dare il valore restituito dall'algoritmo.

Soluzione

  1. Ricerca di \(m = 22\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 15 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 4 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 22 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 22 si trova all'indice 3.

  2. Ricerca di \(m = 15\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 15 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 15 si trova all'indice 1.

  3. Ricerca di \(m = 17\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 15 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 4 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 22 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(4\) 4 8 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(5\) 5 1 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(6\) 6 30 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(7\) 7 17 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 17 si trova all'indice 7.

  4. Ricerca di \(m = 10\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 15 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 4 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 22 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(4\) 4 8 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(5\) 5 1 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(6\) 6 30 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(7\) 7 17 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(-\) 8 \(-\) \(i > n\) \(\Rightarrow\) il ciclo termina, non trovato!

    Quindi, l'elemento 10 non è presente nell'array (restituisce \(-1\)).

  5. Ricerca di \(m = 1\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 15 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 4 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 22 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(4\) 4 8 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(5\) 5 1 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 1 si trova all'indice 5.

Esercizio 4.3: Ricerca lineare e ricerca binaria (E3)

Consideriamo il seguente array:

\[ a = [6, 19, 3, 27, 12, 5, 33] \]

con \(n = 7\).

Domande

  1. Applicare l'algoritmo di ricerca lineare (Linear Search) all'array \(a\) per ciascuno dei seguenti valori cercati:

    1. \(m = 27\)

    2. \(m = 6\)

    3. \(m = 33\)

    4. \(m = 15\)

    5. \(m = 3\)

    Per ogni ricerca, mostrare l'esecuzione passo per passo, indicando a ogni iterazione i valori di \(i\), \(a[i]\) e il risultato del confronto, e dare il valore restituito dall'algoritmo.

Soluzione

  1. Ricerca di \(m = 27\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 6 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 19 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 3 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(4\) 4 27 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 27 si trova all'indice 4.

  2. Ricerca di \(m = 6\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 6 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 6 si trova all'indice 1.

  3. Ricerca di \(m = 33\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 6 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 19 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 3 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(4\) 4 27 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(5\) 5 12 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(6\) 6 5 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(7\) 7 33 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 33 si trova all'indice 7.

  4. Ricerca di \(m = 15\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 6 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 19 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 3 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(4\) 4 27 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(5\) 5 12 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(6\) 6 5 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(7\) 7 33 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(-\) 8 \(-\) \(i > n\) \(\Rightarrow\) il ciclo termina, non trovato!

    Quindi, l'elemento 15 non è presente nell'array (restituisce \(-1\)).

  5. Ricerca di \(m = 3\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 6 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 19 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 3 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 3 si trova all'indice 3.

Esercizio 4.4: Ricerca lineare e ricerca binaria (E4)

Consideriamo il seguente array:

\[ a = [50, 25, 75, 10, 40, 60, 5] \]

con \(n = 7\).

Domande

  1. Applicare l'algoritmo di ricerca lineare (Linear Search) all'array \(a\) per ciascuno dei seguenti valori cercati:

    1. \(m = 10\)

    2. \(m = 50\)

    3. \(m = 5\)

    4. \(m = 30\)

    5. \(m = 75\)

    Per ogni ricerca, mostrare l'esecuzione passo per passo, indicando a ogni iterazione i valori di \(i\), \(a[i]\) e il risultato del confronto, e dare il valore restituito dall'algoritmo.

Soluzione

  1. Ricerca di \(m = 10\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 50 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 25 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 75 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(4\) 4 10 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 10 si trova all'indice 4.

  2. Ricerca di \(m = 50\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 50 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 50 si trova all'indice 1.

  3. Ricerca di \(m = 5\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 50 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 25 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 75 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(4\) 4 10 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(5\) 5 40 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(6\) 6 60 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(7\) 7 5 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 5 si trova all'indice 7.

  4. Ricerca di \(m = 30\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 50 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 25 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 75 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(4\) 4 10 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(5\) 5 40 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(6\) 6 60 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(7\) 7 5 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(-\) 8 \(-\) \(i > n\) \(\Rightarrow\) il ciclo termina, non trovato!

    Quindi, l'elemento 30 non è presente nell'array (restituisce \(-1\)).

  5. Ricerca di \(m = 75\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 50 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 25 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 75 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 75 si trova all'indice 3.

Esercizio 4.5: Ricerca lineare e ricerca binaria (E5)

Consideriamo il seguente array:

\[ a = [11, 7, 3, 18, 24, 9, 16, 2] \]

con \(n = 8\).

Domande

  1. Applicare l'algoritmo di ricerca lineare (Linear Search) all'array \(a\) per ciascuno dei seguenti valori cercati:

    1. \(m = 24\)

    2. \(m = 11\)

    3. \(m = 2\)

    4. \(m = 8\)

    5. \(m = 3\)

    Per ogni ricerca, mostrare l'esecuzione passo per passo, indicando a ogni iterazione i valori di \(i\), \(a[i]\) e il risultato del confronto, e dare il valore restituito dall'algoritmo.

Soluzione

  1. Ricerca di \(m = 24\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 11 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 7 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 3 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(4\) 4 18 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(5\) 5 24 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 24 si trova all'indice 5.

  2. Ricerca di \(m = 11\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 11 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 11 si trova all'indice 1.

  3. Ricerca di \(m = 2\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 11 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 7 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 3 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(4\) 4 18 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(5\) 5 24 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(6\) 6 9 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(7\) 7 16 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(8\) 8 2 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 2 si trova all'indice 8.

  4. Ricerca di \(m = 8\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 11 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 7 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 3 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(4\) 4 18 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(5\) 5 24 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(6\) 6 9 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(7\) 7 16 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(8\) 8 2 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(-\) 9 \(-\) \(i > n\) \(\Rightarrow\) il ciclo termina, non trovato!

    Quindi, l'elemento 8 non è presente nell'array (restituisce \(-1\)).

  5. Ricerca di \(m = 3\):

    iterazione \(i\) \(a[i]\) azione
    \(1\) 1 11 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(2\) 2 7 \(a[i] \neq m\) \(\Rightarrow\) continua
    \(3\) 3 3 \(a[i] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 3 si trova all'indice 3.

Esercizio 4.6: Ricerca lineare e ricerca binaria (E6)

Consideriamo il seguente array, ordinato in modo non decrescente:

\[ a = [2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78, 89] \]

con \(n = 12\).

Domande

  1. Applicare l'algoritmo di ricerca binaria (Binary Search) all'array \(a\) per ciascuno dei seguenti valori cercati:

    1. \(m = 23\)

    2. \(m = 2\)

    3. \(m = 89\)

    4. \(m = 50\)

    5. \(m = 1\)

    Per ogni ricerca, mostrare l'esecuzione passo per passo, indicando a ogni iterazione i valori di \(left\), \(right\), \(mid\), \(a[mid]\) e il risultato del confronto, e dare il valore restituito dall'algoritmo.

Soluzione

  1. Ricerca di \(m = 23\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 12 6 23 \(a[mid] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 23 si trova all'indice 6.

  2. Ricerca di \(m = 2\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 12 6 23 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 5\)
    \(2\) 1 5 3 8 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 2\)
    \(3\) 1 2 1 2 \(a[mid] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 2 si trova all'indice 1.

  3. Ricerca di \(m = 89\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 12 6 23 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 7\)
    \(2\) 7 12 9 56 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 10\)
    \(3\) 10 12 11 78 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 12\)
    \(4\) 12 12 12 89 \(a[mid] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 89 si trova all'indice 12.

  4. Ricerca di \(m = 50\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 12 6 23 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 7\)
    \(2\) 7 12 9 56 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 8\)
    \(3\) 7 8 7 38 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 8\)
    \(4\) 8 8 8 45 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 9\)
    \(-\) 9 8 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Non trovato!

    Quindi, l'elemento 50 non è presente nell'array (restituisce \(-1\)).

  5. Ricerca di \(m = 1\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 12 6 23 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 5\)
    \(2\) 1 5 3 8 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 2\)
    \(3\) 1 2 1 2 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 0\)
    \(-\) 1 0 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Non trovato!

    Quindi, l'elemento 1 non è presente nell'array (restituisce \(-1\)).

Esercizio 4.7: Ricerca lineare e ricerca binaria (E7)

Consideriamo il seguente array, ordinato in modo non decrescente:

\[ a = [1, 3, 5, 7, 9, 11, 13, 15] \]

con \(n = 8\).

Domande

  1. Applicare l'algoritmo di ricerca binaria (Binary Search) all'array \(a\) per ciascuno dei seguenti valori cercati:

    1. \(m = 7\)

    2. \(m = 1\)

    3. \(m = 15\)

    4. \(m = 10\)

    5. \(m = 20\)

    Per ogni ricerca, mostrare l'esecuzione passo per passo, indicando a ogni iterazione i valori di \(left\), \(right\), \(mid\), \(a[mid]\) e il risultato del confronto, e dare il valore restituito dall'algoritmo.

Soluzione

  1. Ricerca di \(m = 7\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 8 4 7 \(a[mid] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 7 si trova all'indice 4.

  2. Ricerca di \(m = 1\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 8 4 7 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 3\)
    \(2\) 1 3 2 3 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 1\)
    \(3\) 1 1 1 1 \(a[mid] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 1 si trova all'indice 1.

  3. Ricerca di \(m = 15\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 8 4 7 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 5\)
    \(2\) 5 8 6 11 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 7\)
    \(3\) 7 8 7 13 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 8\)
    \(4\) 8 8 8 15 \(a[mid] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 15 si trova all'indice 8.

  4. Ricerca di \(m = 10\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 8 4 7 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 5\)
    \(2\) 5 8 6 11 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 5\)
    \(3\) 5 5 5 9 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 6\)
    \(-\) 6 5 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Non trovato!

    Quindi, l'elemento 10 non è presente nell'array (restituisce \(-1\)).

  5. Ricerca di \(m = 20\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 8 4 7 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 5\)
    \(2\) 5 8 6 11 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 7\)
    \(3\) 7 8 7 13 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 8\)
    \(4\) 8 8 8 15 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 9\)
    \(-\) 9 8 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Non trovato!

    Quindi, l'elemento 20 non è presente nell'array (restituisce \(-1\)).

Esercizio 4.8: Ricerca lineare e ricerca binaria (E8)

Consideriamo il seguente array, ordinato in modo non decrescente:

\[ a = [10, 20, 30, 40, 50, 60] \]

con \(n = 6\).

Domande

  1. Applicare l'algoritmo di ricerca binaria (Binary Search) all'array \(a\) per ciascuno dei seguenti valori cercati:

    1. \(m = 40\)

    2. \(m = 10\)

    3. \(m = 60\)

    4. \(m = 25\)

    5. \(m = 70\)

    Per ogni ricerca, mostrare l'esecuzione passo per passo, indicando a ogni iterazione i valori di \(left\), \(right\), \(mid\), \(a[mid]\) e il risultato del confronto, e dare il valore restituito dall'algoritmo.

Soluzione

  1. Ricerca di \(m = 40\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 6 3 30 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 4\)
    \(2\) 4 6 5 50 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 4\)
    \(3\) 4 4 4 40 \(a[mid] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 40 si trova all'indice 4.

  2. Ricerca di \(m = 10\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 6 3 30 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 2\)
    \(2\) 1 2 1 10 \(a[mid] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 10 si trova all'indice 1.

  3. Ricerca di \(m = 60\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 6 3 30 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 4\)
    \(2\) 4 6 5 50 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 6\)
    \(3\) 6 6 6 60 \(a[mid] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 60 si trova all'indice 6.

  4. Ricerca di \(m = 25\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 6 3 30 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 2\)
    \(2\) 1 2 1 10 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 2\)
    \(3\) 2 2 2 20 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 3\)
    \(-\) 3 2 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Non trovato!

    Quindi, l'elemento 25 non è presente nell'array (restituisce \(-1\)).

  5. Ricerca di \(m = 70\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 6 3 30 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 4\)
    \(2\) 4 6 5 50 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 6\)
    \(3\) 6 6 6 60 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 7\)
    \(-\) 7 6 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Non trovato!

    Quindi, l'elemento 70 non è presente nell'array (restituisce \(-1\)).

Esercizio 4.9: Ricerca lineare e ricerca binaria (E9)

Consideriamo il seguente array, ordinato in modo non decrescente:

\[ a = [4, 8, 15, 16, 23, 42] \]

con \(n = 6\).

Domande

  1. Applicare l'algoritmo di ricerca binaria (Binary Search) all'array \(a\) per ciascuno dei seguenti valori cercati:

    1. \(m = 15\)

    2. \(m = 4\)

    3. \(m = 42\)

    4. \(m = 20\)

    5. \(m = 2\)

    Per ogni ricerca, mostrare l'esecuzione passo per passo, indicando a ogni iterazione i valori di \(left\), \(right\), \(mid\), \(a[mid]\) e il risultato del confronto, e dare il valore restituito dall'algoritmo.

Soluzione

  1. Ricerca di \(m = 15\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 6 3 15 \(a[mid] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 15 si trova all'indice 3.

  2. Ricerca di \(m = 4\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 6 3 15 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 2\)
    \(2\) 1 2 1 4 \(a[mid] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 4 si trova all'indice 1.

  3. Ricerca di \(m = 42\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 6 3 15 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 4\)
    \(2\) 4 6 5 23 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 6\)
    \(3\) 6 6 6 42 \(a[mid] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 42 si trova all'indice 6.

  4. Ricerca di \(m = 20\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 6 3 15 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 4\)
    \(2\) 4 6 5 23 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 4\)
    \(3\) 4 4 4 16 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 5\)
    \(-\) 5 4 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Non trovato!

    Quindi, l'elemento 20 non è presente nell'array (restituisce \(-1\)).

  5. Ricerca di \(m = 2\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 6 3 15 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 2\)
    \(2\) 1 2 1 4 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 0\)
    \(-\) 1 0 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Non trovato!

    Quindi, l'elemento 2 non è presente nell'array (restituisce \(-1\)).

Esercizio 4.10: Ricerca lineare e ricerca binaria (E10)

Consideriamo il seguente array, ordinato in modo non decrescente:

\[ a = [3, 6, 9, 12, 15, 18, 21, 24, 27, 30] \]

con \(n = 10\).

Domande

  1. Applicare l'algoritmo di ricerca binaria (Binary Search) all'array \(a\) per ciascuno dei seguenti valori cercati:

    1. \(m = 18\)

    2. \(m = 3\)

    3. \(m = 30\)

    4. \(m = 10\)

    5. \(m = 35\)

    Per ogni ricerca, mostrare l'esecuzione passo per passo, indicando a ogni iterazione i valori di \(left\), \(right\), \(mid\), \(a[mid]\) e il risultato del confronto, e dare il valore restituito dall'algoritmo.

Soluzione

  1. Ricerca di \(m = 18\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 10 5 15 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 6\)
    \(2\) 6 10 8 24 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 7\)
    \(3\) 6 7 6 18 \(a[mid] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 18 si trova all'indice 6.

  2. Ricerca di \(m = 3\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 10 5 15 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 4\)
    \(2\) 1 4 2 6 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 1\)
    \(3\) 1 1 1 3 \(a[mid] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 3 si trova all'indice 1.

  3. Ricerca di \(m = 30\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 10 5 15 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 6\)
    \(2\) 6 10 8 24 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 9\)
    \(3\) 9 10 9 27 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 10\)
    \(4\) 10 10 10 30 \(a[mid] = m\) \(\Rightarrow\) Trovato!

    Quindi, l'elemento 30 si trova all'indice 10.

  4. Ricerca di \(m = 10\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 10 5 15 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 4\)
    \(2\) 1 4 2 6 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 3\)
    \(3\) 3 4 3 9 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 4\)
    \(4\) 4 4 4 12 \(a[mid] > m\) \(\Rightarrow\) \(right \leftarrow 3\)
    \(-\) 4 3 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Non trovato!

    Quindi, l'elemento 10 non è presente nell'array (restituisce \(-1\)).

  5. Ricerca di \(m = 35\):

    iterazione \(left\) \(right\) \(mid\) \(a[mid]\) azione
    \(1\) 1 10 5 15 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 6\)
    \(2\) 6 10 8 24 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 9\)
    \(3\) 9 10 9 27 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 10\)
    \(4\) 10 10 10 30 \(a[mid] < m\) \(\Rightarrow\) \(left \leftarrow 11\)
    \(-\) 11 10 \(-\) \(-\) \(left > right\) \(\Rightarrow\) Non trovato!

    Quindi, l'elemento 35 non è presente nell'array (restituisce \(-1\)).