Ricerca lineare

Lezione 9 di 26 del corso Gli array in C++ di Coddy.

Per cercare un elemento richiesto in un array, usiamo un metodo semplice chiamato ricerca lineare.

Come suggerisce il nome, richiede un tempo lineare, ovvero un tempo O(n) per cercare un elemento, poiché dobbiamo scorrere l'intero array per trovare il numero richiesto.

Supponiamo che k sia l'elemento che dobbiamo trovare e che sia dato un array. Dobbiamo scorrere l'intero array e, se troviamo l'elemento, dobbiamo stampare YES, altrimenti stampiamo NO.

for(int i=0;i<n;i++){
   if(arr[i]==k){
     cout<<"YES"<<endl;
   }else{
     cout<<"NO"<<endl;
   }
}

Analisi della complessità temporale

Il caso migliore che può verificarsi è che l'elemento che stiamo cercando si trovi al primo indice; in tal caso, richiederà un tempo costante. Il caso peggiore si verifica se l'elemento si trova all'ultimo indice, e allora la complessità temporale è dell'ordine di n. Pertanto, la complessità temporale della ricerca lineare è O(n), dove n è il numero di elementi in un array.

Sfida

Dato un array, trova la somma di tutti gli elementi dell'array.

Provalo tu

#include<iostream>
using namespace std;

int main(){

 
  int n;
  cin>>n;

  int arr[n];
  
  for(int i=0;i<n;i++){
    cin>>arr[i];
  }
  

 //Write your code here 





    return 0;
}