Ricerca

Lezione 20 di 23 del corso C++ - Libreria standard dei template di Coddy.

La ricerca è il processo di individuazione della posizione di un elemento specifico in una sequenza di elementi.

Un algoritmo di ricerca è un algoritmo a cui viene fornito un argomento x e che prova a trovare un elemento il cui valore è x in un insieme di valori dato. Pertanto, la ricerca di un elemento con quel valore potrebbe non riuscire se tale elemento non esiste.

Esistono diverse tecniche e metodi di ricerca, ma in C++ imparerai a conoscere:

Ricerca lineare
Ricerca binaria

Ricerca lineare

La ricerca lineare è la tecnica di ricerca più basilare ed è anche facile da implementare in C++. Come puoi intuire dal nome, nella ricerca lineare la chiave da cercare viene confrontata in modo lineare con ogni elemento della sequenza di dati, finché non viene trovata o la sequenza termina.

Linear Search(sequence, key)
	for each item in sequence:
		if item == key
			return item's index

Nel codice reale, la ricerca lineare apparirà più o meno così:

int linear_search(int array[], int n, int x)
{
	for(int i = 0; i < n; i++)
		if(array[i] == x)
			return i;
	return 0;
}

int main()
{
	int array[] = {1, 2, 3, 4, 5};
	int n = 5;
	int x = 3;
	
	cout << "The index of the element " << x << " is " << linear_search(array, n, x);

Output:
The index of the element 3 is 2

Come puoi vedere dal codice qui sopra, la funzione di ricerca lineare scorre la sequenza di elementi finché non trova una corrispondenza; se non la trova, restituisce -1.

Ricerca binaria

La ricerca binaria è un algoritmo di ricerca che permette di trovare la posizione di un elemento, ma l'array deve essere ordinato.
L'algoritmo di ricerca binaria usa la tecnica "divide et impera" per cercare la chiave. L'elenco degli elementi viene diviso ripetutamente a metà e si cerca l'elemento nella metà più vicina.

Supponiamo di cercare l'elemento x = 4

impostazione dei puntatori nella ricerca binaria

ricerca dell'elemento centrale nella ricerca binaria

Ecco come apparirà il codice per la ricerca binaria.

int binarySearch(int array[], int x, int left, int right) {
  
  while (left <= right) {
    int mid = left + (right - left) / 2;

    if (array[mid] == x)
      return mid;

    if (array[mid] < x)
      left = mid + 1;

    else
      right  = mid - 1;
  }

  return -1;
}

int main()
{
    int array[] = {1, 5, 8, 10, 20};
    int x = 10;
    int n = 5;
    int result = binarySearch(array, x, 0, n - 1);
    
    if(result == -1)
    	cout << "Not found.";
    else
    	cout << "The element is found at " << result;

Output:
The element is found at 3

Ricorda cos'è la ricerca, qual è il suo scopo e per cosa l'abbiamo usata. Ricorda come implementare la ricerca lineare e la ricerca binaria. Continua a esercitarti con le tecniche avanzate in C++ attraverso gli esercizi.

Sfida

Medio

Ti vengono forniti 10 numeri in input. Nella riga successiva c'è un numero N. Nella terza riga ci sono N numeri che indicano le posizioni degli elementi da visualizzare sullo schermo.

Input
10 20 30 40 50 60 70 80 90 100
3
20
50
80

Output
1 4 7

Provalo tu

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// Enter your code here

int main()
{
    // Enter your code here

    return 0;
}