Tìm kiếm tuyến tính

Bài học 9 trên 26 trong khóa học Mảng trong C++ của Coddy.

Để tìm một phần tử cần thiết trong mảng, ta dùng một phương pháp đơn giản gọi là tìm kiếm tuyến tính.

Đúng như tên gọi, phương pháp này cần thời gian tuyến tính, nghĩa là thời gian O(n) để tìm một phần tử, vì ta phải duyệt qua toàn bộ mảng để tìm số cần tìm.

Giả sử k là phần tử cần tìm và ta có một mảng. Ta phải duyệt qua toàn bộ mảng. Nếu tìm thấy phần tử đó, ta in ra YES, nếu không thì in ra NO.

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

Phân tích độ phức tạp thời gian

Trường hợp tốt nhất có thể xảy ra là phần tử cần tìm nằm ở chỉ số đầu tiên. Khi đó, việc tìm kiếm chỉ mất thời gian hằng số. Trường hợp xấu nhất là phần tử nằm ở chỉ số cuối cùng, khi đó độ phức tạp thời gian là bậc n. Vì vậy, độ phức tạp thời gian của tìm kiếm tuyến tính là O(n), trong đó n là số phần tử trong mảng.

Thử thách

Cho một mảng, hãy tìm tổng của tất cả phần tử trong mảng.

Tự làm thử

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