[Musik spiller] DOUG LLOYD: Lineær søgning er en algoritme, vi kan bruge til at finde et element i et array. En algoritme tilbagekaldelse er en trin-for-trin sæt af instruktioner til at fuldføre en opgave. 

Den lineære søgning Algoritmen fungerer således. Gentage tværs array fra venstre til ret, på udkig efter en specificeret element. 

I pseudokode, som er en mere destilleret udgave af denne sætning, Hvis det første element er det du leder efter, kan du stoppe. Ellers gå videre til næste element, og holde går igen og igen, indtil du finder elementet, eller du ikke. Så vi kan bruge den lineære søgealgoritme, f.eks at finde målværdien ni i dette array. Nå vi starter ved begyndelsen. Hvis det er, hvad vi er leder efter, kan vi stoppe. Det er ikke, vi er ikke på udkig efter 11. Så ellers gå til næste element. 

Så vi ser på 23. Er 23, hvad vi leder efter? Nå nej, så vi går videre til den næste element, og det næste element, og vi holder gå gennem denne proces igen og igen og over, indtil vi lander på en situation som denne. 

Ni er, hvad vi leder efter, og dette element i arrayet er, er det værdi er ni. Og så vi fundet, hvad vi er leder efter, og vi kan stoppe. Den lineære søgning har afsluttet med succes. 

Men hvad hvis vi leder efter et element, der er ikke i vores array. Er lineær søgning stadig arbejde? Godt sikker. Så vi gentage denne proces starter ved det første element. Hvis det er, hvad vi er leder efter, kan vi stoppe. Det er det ikke. Ellers, vi flytter til det næste element. 

Men vi kan holde gentage denne proces, undersøge hvert element til gengæld håber, at vi finder det nummer 50. Men vi vil ikke vide, om vi har fundet det nummer 50 eller hvis vi ikke gjorde det, indtil vi har trådt over hvert enkelt element i arrayet. 

Først når vi har gjort det og komme op kort, kan vi konkludere, 50 er ikke i array'et. Og så den lineære søgning algoritme, godt det mislykkedes, per se. Men ikke i den forstand, at det lykkedes i at gøre, hvad spurgte vi det at gøre. 

Det lykkedes i så meget, som det ikke fandt 50, men 50 var ikke i array'et. Men vi har udtømmende søgt gennem hver enkelt element og så, mens vi ikke finde noget, lineær søgning stadig lykkes, selv om element ikke er i array'et. 

Så hvad er den værste fald scenarie med lineær søgning? Nå vi er nødt til at se gennem hvert enkelt element, enten fordi måldelen er det sidste element i arrayet, eller det element, vi leder efter ikke faktisk eksisterer i arrayet overhovedet. Hvad er den bedste tænkelige scenarie? Godt vi kan finde den element samme. Og hvor mange elementer skal vi så nødt til at se ved i bedste fald, hvis vi leder efter det og vi finder det i starten? Vi kan stoppe øjeblikkeligt. 

Hvad siger det om kompleksiteten af ​​lineær søgning? Godt i værste fald har vi at se på hvert enkelt element. Og så det kører i O i n, i værste fald. 

I bedste fald, vi skal finde elementet med det samme. Og så kører i omega på 1. 

Jeg er Doug Lloyd. Det er CS50.