[Speel van musiek] DOUG LLOYD: Lineêre soek is 'n algoritme ons kan gebruik om 'n element in 'n skikking te vind. 'N algoritme herroep is 'n stel stap-vir-stap instruksies vir die voltooiing van 'n taak. 

Die lineêre soek algoritme werk soos volg. Itereer oor die skikking van links na reg, op soek na 'n gespesifiseerde element. 

In pseudokode, wat 'n meer gedistilleerde weergawe van hierdie sin, As die eerste element is wat jy soek, kan jy stop. Anders, skuif na die volgende element en hou oor en oor gaan totdat jy die element, of jy doen nie. So kan ons die lineêre gebruik soek algoritme, byvoorbeeld, om die teiken waarde vind nege in hierdie reeks. Wel ons begin by die begin. As dit is wat ons is soek, kan ons stop. Dit is nie, ons is nie op soek na 11. So anders, skuif na die volgende element. 

So ons kyk na 23. Is 23 wat ons soek? Wel nee, sodat ons beweeg op na die volgende element, en die volgende element, en ons hou gaan deur hierdie proses oor en oor en oor, totdat ons land op 'n situasie soos hierdie. 

Nege is wat ons soek, en hierdie element van die skikking is, is dit se waarde is nege. En so het ons gevind wat ons soek, en ons kan stop. Die lineêre soek het voltooi, suksesvol. 

Maar wat van as ons is op soek na 'n element wat nie in ons verskeidenheid. Maak lineêre soek nog werk? Wel seker. Sodat ons hierdie proses herhaal begin by die eerste element. As dit is wat ons is soek, kan ons stop. Dit is nie. Anders, beweeg ons na die volgende element. 

Maar ons kan hou herhaal hierdie proses, ondersoek elke element in sy beurt, hoop dat ons die nommer 50. Maar ons sal nie weet as ons het die nommer 50 gevind of as ons het nie, totdat ons het uitgetree oor elke enkele element van die skikking. 

Slegs een keer wat ons gedoen het wat en kom kort, kan ons aflei dat 50 is nie in die skikking. En so het die lineêre soek algoritme, goed dit misluk, per se. Maar nie in die sin dat dit was onsuksesvol in te doen wat ons gevra om dit te doen. 

Dit was onsuksesvol in as veel as dit nie vind 50, maar 50 was nie in die skikking. Maar ons het uitvoerig gesoek deur elke enkele element en so, terwyl ons nie vind enigiets, lineêre soek steeds slaag selfs al is die element is nie in die skikking. 

So, wat is die ergste geval scenario met lineêre soek? Wel, ons het om te kyk deur elke enkele element, óf omdat die teiken element is die laaste element van die skikking, of die element wat ons soek nie werklik bestaan ​​in die skikking nie. Wat is die beste scenario? Wel, ons kan vind die element onmiddellik. En hoeveel elemente het ons dan om te kyk op in die beste geval, As ons kyk na dit en ons vind dit heel aan die begin? Ons kan onmiddellik stop. 

Wat sê dit oor die kompleksiteit van lineêre soek? Wel, in die ergste geval, ons het om te kyk na elke enkele element. En so het dit loop in O van n, in die ergste geval. 

In die beste geval, ons gaan vind die element onmiddellik. En so loop in omega van 1. 

Ek is Doug Lloyd. Dit is CS50.