[Muziek] DOUG LLOYD: Linear search is een algoritme dat we kunnen gebruiken om een ​​element in een array zijn. Een algoritme recall is een set van stap-voor-stap instructies voor het uitvoeren van een taak. 

De lineaire zoekopdracht algoritme werkt als volgt. Herhalen tegenover de array van links naar rechts, op zoek naar een bepaald element. 

In pseudocode, die een gedistilleerd versie van deze zin, wanneer het eerste element is wat u zoekt, kunt u stoppen. Anders naar het volgende element en houden over en over te gaan tot u het element, of je doet het niet. Dus we kunnen de lineaire gebruiken zoekalgoritme bijvoorbeeld aan de streefwaarde te vinden negen in deze array. Nou we beginnen bij het begin. Als het is wat we zijn zoekt, kunnen we stoppen. Het is niet, we zijn niet op zoek naar 11. Dus anders naar het volgende element. 

Dus we kijken naar 23. 23 is wat we zoeken? Nou nee, dus we gaan naar de volgende element en het volgende element, en we blijven gaan door dit proces over en voorbij en over, totdat we landen op een situatie als deze. 

Negen is wat we zoeken, en dit element van de array is, is de waarde van negen. En dus we vonden wat we zoekt, en we kunnen stoppen. De lineaire zoekopdracht heeft afgerond, met succes. 

Maar hoe zit het als we op zoek bent naar een element dat niet in ons aanbod. Heeft lineair zoeken nog steeds werken? Nou zeker. Dus we dit proces herhalen vanaf het eerste element. Als het is wat we zijn zoekt, kunnen we stoppen. Het is niet. Anders gaan we naar het volgende element. 

Maar we kunnen blijven herhalen dit proces, onderzoekt elk element op zijn beurt, in de hoop dat we de nummer 50. Maar we zullen niet weten of we hebben het nummer 50 gevonden of als we dat niet deden, totdat we hebben gestapt dan elk element van de array. 

Alleen als we hebben gedaan dat en komen kort, kunnen we concluderen dat 50 niet in de array. En zo het lineair zoeken algoritme, goed het niet per se. Maar niet in de zin dat het was niet succesvol in het doen wat vroegen we om te doen. 

Het was niet succesvol in als veel als het niet vinden 50, maar 50 was niet in de array. Maar we hebben uitvoerig gezocht door middel van elk element en zo, terwijl we niet vinden iets, lineair zoeken nog steeds slaagt zelfs indien de element niet in de array. 

Dus wat is het ergste geval scenario met lineair zoeken? Nou moeten we kijken door elk element, hetzij omdat het doelelement is het laatste element van de array, of het element we zoeken niet werkelijk bestaan ​​in de matrix helemaal. Wat is de beste case scenario? Goed we kunnen vinden van de element onmiddellijk. En hoeveel elementen moeten we dan kijken op de in het gunstigste geval, als we naar op zoek en we vinden het in het begin? We kunnen onmiddellijk stoppen. 

Wat zegt dit over de complexiteit van lineair zoeken? Welnu, in het ergste geval, we hebben om te kijken naar elk element. En zo draait in O van n, in het ergste geval. 

In het beste geval, we gaan vind het element onmiddellijk. En zo loopt aan omega van 1. 

Ik ben Doug Lloyd. Dit is CS50.