Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Lineaire Zoeken]
[Patrick Schmid, Harvard University]
[Dit Is CS50.] [CS50.TV]
Zoeken is iets dat je waarschijnlijk vaker doen dan je denkt.
Vanzelfsprekend heeft iedere keer dat u een web browser
en zoeken naar een webpagina -
of zoeken naar je vrienden op je favoriete social networking site -
u zoekt.
Maar dat is slechts een klein deel van het zoeken die je doet op een dagelijkse basis.
Als u wilt dat een blauw shirt te vinden in de kast,
of die perfecte rode blouse voor de gelegenheid,
u zoekt.
Als je naar een winkel die je nog nooit geweest bent voor,
en je bent op zoek naar de broccoli in de producten gangpad
u zoekt.
Wat je misschien begonnen te merken
is dat afhankelijk van wat je zoekt
of hoe de items zijn geordend als u op zoek bent voor hen
het heeft een invloed op de manier waarop u zoeken.
Bijvoorbeeld, als uw shirts zijn opknoping in de kast,
kunt u waarschijnlijk gewoon uitpikken zonder veel te zoeken.
Als je ervan uitgaande dat je hoeft te lopen door het gangpad
om de broccoli te krijgen, heeft u waarschijnlijk om te kijken naar alle andere groenten
voordat je dat broccoli.
Lineaire Search is een voorbeeld van een dergelijke zoekmethode - of algoritme.
Zoals de naam al impliceert,
Deze methode zoekt een item in een lineair na elkaar.
Dus, als u op zoek bent naar de resultaten van uw favoriete zoekmachine
en je leest door de lijst met resultaten,
u gebruik maakt van lineair zoeken.
Oke. Laten we eens kijken naar een voorbeeld.
Zeggen dat we een lijst van nummers - 2, 4, 0, 5, 3, 7, 8, en 1 -
en we zijn op zoek naar het getal 0.
Uiteraard kunt u gewoon zien dat de 0 is in de derde positie.
Maar, een computerprogramma is niet zo fortuinlijk.
Het kan alleen "zien" cijfer tegelijk.
Dus, vanaf het begin van de lijst
het alleen "ziet" de 2.
Het programma controleert vervolgens - is 2 gelijk is aan 0?
Duidelijk niet. Dus het gaat verder met het volgende nummer, 4.
Heeft 4 gelijke 0? Nope.
De volgende, 0. Ah! Nul is gelijk aan 0.
Daar hebben we het! Het is in de derde positie.
Oke. Laten we eens kijken naar een aantal pseudo-code.
Het is slechts een paar regels lang, maar laten we eens kijken naar het een regel per keer.
Ten eerste, laten we definiƫren de functie - en we gaan om te spreken van lineaire zoeken -
en het duurt twee argumenten - toets en array.
De sleutel is dat waarde die we zoeken,
zodat in het vorige voorbeeld, dat was nul.
Een array is een lijst van nummers
dat beschikt over alle waarden die we gaan zoeken.
Dus, wat we willen doen is dat we willen kijken -
van alle posities, vanaf het begin van de array
til het einde van de array - dus de lengte van de array -
kijken naar elke positie en controleer elk een.
Dus dat is wat die "voor" lus doet.
En op elke positie, we gaan om te zeggen
"Is dat waarde op dat de huidige positie gelijk is aan de sleutel die we zoeken? '
Dus - in het vorige voorbeeld weer, sleutel was 0 -
dus wij zeggen: "Is de array op positie i gelijk aan nul?"
Als het is, we gaan 'i' terug te keren, want dat is de huidige positie we op.
Dus in het vorige voorbeeld,
dat was de derde positie.
Als we hebben meegemaakt de hele array
en we hebben niets gevonden -
dus laten we zeggen dat we op zoek waren naar het nummer 500
die duidelijk niet in dit voorbeeld -
we moeten iets terug,
en we gaan op -1 terug te keren.
En we gewoon terug te keren -1 omdat dat is een positie
die niet bestaat in de array.
En dus dat betekent dat als je het terug te krijgen van een functie
het zegt: "Hmm, oke. Ik denk dat ik niet alles vinden.
Dus dat 500 nooit was daar. "
Het leuke van lineair zoeken is dat
het zal werken op een lijst van items,
ongeacht hoe de items worden besteld.
Het maakt niet uit waar de broccoli in de producten gangpad.
Zolang je loopt door het gangpad van het begin tot het einde,
je bent gebonden om het te vinden,
ervan uitgaande dat de winkel nog niet op is van broccoli, natuurlijk.
Maar het is de grootste kracht is ook zijn grootste zwakte.
Stel dat je een lijst van tweehonderd nummers
die gesorteerd van 1 tot 200.
Als u op zoek bent naar het nummer 198,
je moet bijna de gehele lijst met nummers zoeken
voordat je degene die je zoekt.
Er moet een betere manier zijn!
Wees gerust er is.
Maar, dat is een onderwerp voor een andere video.
Ook wees maar niet ***!
Gewoon omdat lineair zoeken is niet de beste oplossing in alle situaties,
het betekent niet dat het niet van pas komen.
Anders, hoe zou u merken dat broccoli in de producten gangpad?
Mijn naam is Patrick Schmid, en dit is CS50.
[CS50.TV]