[MUSIK SPELA] DOUG LLOYD: Linjär sökning är en algoritm som vi kan använda för att hitta ett element i en array. En algoritm återkallande är ett steg-för-steg set instruktioner för att fylla en uppgift. 

Den linjära sökning Algoritmen fungerar enligt följande. Iterera över uppsättningen från vänster till höger, letar efter en viss del. 

I pseudokod, som är ett mer destillerad version av denna mening, om det första elementet är vad du letar efter, kan du sluta. Annars flyttar till nästa element och fortsätt om och om igen tills du hittar elementet, eller du inte. Så vi kan använda det linjära sökalgoritm, till exempel, att hitta målvärdet nio i denna samling. Jo vi börjar från början. Om det är vad vi är söker, kan vi sluta. Det är inte, vi är inte ute efter 11. Så annars, gå till nästa element. 

Så vi tittar på 23. Är 23 det vi letar efter? Jo nej, så vi går vidare till nästa elementet, och nästa element, och vi håller gå igenom denna process om och om igen och över, tills vi landar på en situation som denna. 

Nio är vad vi letar efter, och denna del av gruppen är, är det värde nio. Och så fann vi vad vi är letar efter, och vi kan sluta. Den linjära sökningen har klar, framgångsrikt. 

Men vad händer om vi letar efter ett element som inte är i vårt utbud. Har linjär sökning fortfarande fungerar? Väl säker. Så vi upprepa denna process med början vid det första elementet. Om det är vad vi är söker, kan vi sluta. Det är inte. Annars, vi flyttar till nästa element. 

Men vi kan fortsätta att upprepa denna process, undersöka varje element i sin tur hoppas att vi hittar numret 50. Men vi kommer inte att veta om vi har hittat numret 50 eller om vi inte förrän vi har klivit över varje enskilt element i matrisen. 

Först när vi har gjort det och komma upp kort, kan vi konstatera att 50 är inte i arrayen. Och så den linjära sökningen algoritm, ja det inte i sig. Men inte i den meningen att den lyckades inte göra det vi bett den att göra. 

Det lyckades inte så mycket som det inte hittade 50, men 50 var inte i arrayen. Men vi har uttömmande sökt genom varje enskilt element och så, medan vi hittade inte något, linjär sökning fortfarande lyckas även om elementet är inte i arrayen. 

Så vad är det värsta fallet scenario med linjär sökning? Jo vi måste titta igenom varje enskilt element, antingen för att målelementet är det sista elementet i arrayen, eller elementet vi söker inte faktiskt finns i arrayen huvudtaget. Vad är det bästa scenariot? Jo vi kan hitta den elementet omedelbart. Och hur många element har måste vi se på i bästa fall, Om vi ​​letar efter det och vi tycker att det i början? Vi kan sluta omedelbart. 

Vad säger detta om komplexitet linjär sökning? Väl i värsta fall, vi har att titta på varje enskilt element. Och så det körs i O n, i värsta fall. 

I bästa fall, vi ska hitta elementet omedelbart. Och så körs i omega 1. 

Jag är Doug Lloyd. Detta är CS50.