חיפוש ליניארי

שיעור 9 מתוך 26 בקורס מערכים ב-C++ של Coddy.

כדי לחפש איבר נדרש במערך, משתמשים בשיטה פשוטה שנקראת חיפוש ליניארי.

כפי שהשם מרמז, הוא דורש זמן ליניארי, כלומר זמן O(n) לחיפוש איבר, מכיוון שעלינו לעבור על המערך כולו כדי למצוא את המספר הנדרש.

נניח ש-k הוא האיבר שעלינו למצוא, ונתון מערך. עלינו לעבור על המערך כולו, ואם מצאנו את האיבר, עלינו להדפיס YES; אחרת, נדפיס NO.

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

ניתוח סיבוכיות הזמן

המקרה הטוב ביותר הוא שהאיבר שאותו אנחנו מחפשים נמצא באינדקס הראשון; במקרה כזה, החיפוש ייקח זמן קבוע. המקרה הגרוע ביותר הוא שהאיבר נמצא באינדקס האחרון, ואז סיבוכיות הזמן היא מסדר n. לכן, סיבוכיות הזמן של חיפוש ליניארי היא O(n), כאשר n הוא מספר האיברים במערך.

אתגר

נתון מערך, מצאו את סכום כל האיברים במערך.

נסו בעצמכם

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