[MUZYKI] DOUG LLOYD: normalny Wyszukiwarka jest to algorytm można użyć, aby znaleźć element w tablicy. Przypomnieć algorytm to zestaw krok po kroku instrukcji do wykonania zadania. 

Wyszukiwanie liniowe Algorytm działa w następujący sposób. Iteracji całej tablicy, od lewej do prawo, szukając określonego elementu. 

W pseudokodzie, który jest bardziej Wersja destylowana tego zdania, Jeśli pierwszy element jest tym, co szukasz, możesz przestać. W przeciwnym razie przejdź do następnego elementu i nie poddawać się w kółko, aż znajdziesz element, albo nie. Tak więc możemy użyć liniowy Algorytm poszukiwania np znaleźć wartość docelową dziewięć w tej tablicy. Dobrze zacząć od początku. Jeśli to, co jesteśmy szukamy, możemy zatrzymać. To nie, my nie szukamy 11. Więc inaczej, przejście do następnego elementu. 

Więc patrzymy na 23. Jest 23, co szukasz? No nie, więc przechodzimy do następnego elementem, a kolejnym elementem, A my wciąż przechodzi ten proces w kółko kółko, aż wylądujemy o takiej sytuacji. 

Dziewięć jest to, czego szukasz, i ten element macierzy jest, to jest wartość nie jest dziewięć. I tak okazało się to, co jesteśmy szuka, a my możemy się zatrzymać. Wyszukiwanie liniowe ma zakończone powodzeniem. 

Ale co, jeśli szukamy element, który nie jest w naszej tablicy. Czy przeszukiwanie liniowe wciąż działa? No pewnie. Więc powtórzyć ten proces począwszy od pierwszego elementu. Jeśli to, co jesteśmy szukamy, możemy zatrzymać. To nie jest. W przeciwnym razie, możemy przejść do następnego elementu. 

Ale możemy powtarzać ten proces, badając każdy element z kolei mając nadzieję, że znajdziemy numer 50. Ale nie wiem, czy Odkryliśmy numer 50 lub jeśli nie, dopóki nie wszedł na każdym elemencie tablicy. 

Tylko raz zrobiliśmy że i wymyślić krótkie, możemy stwierdzić, że 50 nie znajduje się w tablicy. I tak przeszukiwanie liniowe Algorytm, dobrze, że nie udało, per se. Ale w tym sensie, że nie powiodło się w tym, co Poprosiliśmy go zrobić. 

To nie powiodła się, jak podobnie jak nie znaleźliśmy 50, ale 50 nie był w tablicy. Ale my wyczerpująco wyszukiwane przez każdego elementu i tak, a nie znaleźliśmy coś, przeszukiwanie liniowe wciąż powiedzie się, nawet jeśli element ten nie istnieje w tablicy. 

Więc co jest najgorszym przypadku Scenariusz z wyszukiwania liniowego? Cóż musimy patrzeć przez każdy pojedynczy element, albo dlatego, że element docelowy jest to ostatni element tablicy, lub element szukamy nie faktycznie istnieje w tablicy w ogóle. Jaki jest najlepszy scenariusz? Cóż możemy znaleźć Element natychmiast. I jak wiele elementów Czy więc trzeba szukać co w najlepszym przypadku, jeśli szukamy dla niego i znajdujemy go na samym początku? Możemy natychmiast zatrzymać. 

Co nam to mówi o Złożoność wyszukiwania liniowego? Cóż, w najgorszym przypadku, mamy patrzeć na każdego elementu. I tak to działa w O. n, w najgorszym przypadku. 

W najlepszym przypadku, zrobimy natychmiast znaleźć element. I tak trwa w omega 1. 

Jestem Doug Lloyd. To CS50.