Pencarian Linear

Pelajaran 9 dari 26 dalam kursus Array di C++ di Coddy.

Untuk mencari elemen yang diperlukan dalam array, kita menggunakan metode sederhana yang disebut pencarian linear.

Sesuai namanya, metode ini membutuhkan waktu linear, yaitu waktu O(n) untuk mencari sebuah elemen karena kita harus menelusuri seluruh array untuk mendapatkan angka yang diperlukan.

Misalkan k adalah elemen yang harus kita temukan dan sebuah array diberikan. Kita harus menelusuri seluruh array, lalu jika menemukan elemennya, kita harus mencetak YES, jika tidak, kita mencetak NO.

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

Menganalisis kompleksitas waktu

Kemungkinan kasus terbaik adalah elemen yang kita cari berada pada indeks pertama. Dalam kasus itu, waktu yang dibutuhkan adalah waktu konstan. Namun, kasus terburuknya adalah jika elemen tersebut berada pada indeks terakhir, kompleksitas waktunya menjadi O(n). Oleh karena itu, kompleksitas waktu pencarian linear adalah O(n), dengan n sebagai jumlah elemen dalam array.

Tantangan

Diberikan sebuah array, cari jumlah semua elemen dalam array tersebut.

Coba sendiri

#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;
}