[MUZYKI] 

DOUG LLOYD: Wszystko w porządku. Więc przeszukiwanie binarne jest Algorytm możemy użyć znaleźć element wewnątrz tablicy. W przeciwieństwie do wyszukiwania liniowego, wymaga być spełnione specjalne warunki wcześniej, ale jest o wiele bardziej efektywne, jeśli warunek ten jest w rzeczywistości spełnione. 

Więc co to za pomysł tutaj? to dziel i rządź. Chcemy aby zmniejszyć rozmiar obszar wyszukiwania o połowę za każdym razem W celu znalezienia numer docelowy. To jest, gdy warunek wchodzi w grę, choć. Możemy jedynie wykorzystać moc eliminując pół elementów nawet nie patrząc na je jeśli tablica jest posortowana. 

Jeśli jest to kompletne zamieszanie, Nie możemy po prostu z ręki usunięcia połowy elementów, ponieważ nie wiemy, z czym mamy do odrzucenia. Ale jeśli tablica jest posortowana, możemy to zrobić, bo wiem, że wszystko, co do lewej, gdzie obecnie są musi być niższa niż Wartość jesteśmy obecnie. I wszystko, co do Prawo gdzie jesteśmy musi być większa niż wartość jesteśmy obecnie patrząc na. 

Więc co jest pseudokod Kroki wyszukiwania binarnego? Powtarzamy ten proces do czasu tablica lub, jak przejść przez, sub tablice, mniejsze kawałki oryginalna tablica, jest od wielkości 0. Oblicz punkt środkowy bieżącej tablicy pomocniczej. 

Jeśli wartość szukasz jest w tym elemencie tablicy, stop. Znalazłeś to. To wspaniale. W przeciwnym razie, jeśli celem jest mniej niż to, co jest w środku, więc jeśli wartości szukamy na jest niższa niż to, co widzimy, powtórzyć ten proces ponownie, ale zmienić punkt końcowy, zamiast bycia oryginalny wykonać pełny zakres, się na lewo od tego, gdzie właśnie wyglądało. 

Wiedzieliśmy, że w środku była zbyt wysoka, lub celem było mniej niż w połowie, a więc musi istnieć, jeśli to ogóle istnieje w tablicy gdzie z lewej strony środkowego. I tak będziemy ustawić tablicę lokalizacja tuż na lewo punktu środkowego jako nowego punktu końcowego. Z drugiej strony, jeśli celem jest większa niż to, co jest w środku, robimy dokładnie to samo Proces, ale zamiast tego zmienić punkt początkowy będzie na prawo od punktu środkowego po prostu obliczyć. A potem zaczynamy kolejny proces. 

Powiedzmy, wizualizować to, OK? Więc nie wiele się dzieje, a tu, ale tu jest tablica z 15 elementów. I mamy zamiar być śledzenie o wiele więcej rzeczy w tym czasie. Tak więc w poszukiwaniu liniowego, byliśmy po prostu dbanie o cel. Ale tym razem chcemy dbać o tym, gdzie jesteśmy zaczyna wyglądać, gdzie się zatrzymujemy, patrząc, i co to jest punkt środkowy bieżącej tablicy. Więc zaczynamy z wyszukiwaniem binarnym. Jesteśmy prawie dobrze iść, prawda? Idę do wysadzenia poniżej tutaj zestaw wskaźników. Jest to w zasadzie tylko to, co elementem tablicy mówimy. Przy poszukiwaniu liniowego, mamy obchodzi, ponieważ my trzeba wiedzieć, jak wiele Elementy mamy iteracji po, ale w rzeczywistości nie obchodzi, co Element jesteśmy obecnie patrząc na. W poszukiwaniu binarnego, co robimy. A tak, to są po prostu nie jako mały przewodnik. 

Więc możemy zacząć, prawda? No, nie całkiem. Pamiętaj, co powiedziałem o poszukiwaniu binarnym? Nie możemy tego zrobić na zasadzie nieposortowane tablicą lub innego, nie gwarantują, że pewne elementy lub wartości nie są przypadkowym wyrzucić, kiedy tylko zignorować połowę tablicy. 

Więc kroku z wyszukiwaniem binarnym to trzeba mieć posortowaną tablicę. I można użyć dowolnego z sortowania Algorytmy Mówiliśmy o aby dostać się do tej pozycji. Więc teraz, że jesteśmy w miejscu, gdzie możemy wykonać wyszukiwanie binarne. 

Warto więc powtórzyć proces krok po kroku i zachować utwór z tego, co się dzieje, jak idziemy. Więc pierwsze co musimy zrobić to obliczyć punkt środkowy aktualnej tablicy. Cóż, to mówimy, że jesteśmy przede wszystkim, patrząc na wartość 19. Próbujemy znaleźć numer 19. Pierwszy element to Tablica znajduje się na indeksie zerowym, i ostatnim elementem tego Tablica znajduje się na indeks 14. I tak będziemy nazywać te początek i koniec. 

Tak więc obliczyć punkt środkowy przez dodanie 0 plusa 14 podzielone przez 2; bardzo proste punkt środkowy. I można powiedzieć, że punkt środkowy jest obecnie 7. Więc jest 15, co szukasz? Nie, nie jest. Szukamy 19. Ale wiemy, że 19 jest większa niż to, co znaleźliśmy w środku. 

Więc co możemy zrobić, to zmienić punkt początkowy się na prawo z punkt środkowy, i ponownie powtórzyć proces. A kiedy to zrobimy, możemy teraz powiedzieć Nowy punkt początkowy jest lokalizacja tablicy 8. Co mamy skutecznie wykonywane jest ignorowane wszystko z lewej 15. Usunęliśmy połowę problemu, a teraz, Zamiast konieczności wyszukiwania ponad 15 elementy w naszej tablicy, mamy tylko przeszukiwać 7. Więc 8 to nowy punkt początkowy. 14 nadal jest punktem końcowym. 

A teraz idziemy na to jeszcze raz. Obliczamy nowy punkt środkowy. 8 oraz 14 jest 22, dzieli się przez 2 jest 11. Czy to, co szukasz? Nie, nie jest. Szukamy wartości, który jest mniej niż to, co po prostu znaleźć. Tak więc mamy zamiar powtórzyć kolejny proces. Mamy zamiar zmienić punkt końcowy do się na lewo od punktu środkowego. Tak więc nowy punkt końcowy staje się 10. I teraz, że to tylko część tablica mamy do sortowania. Więc mamy teraz wyeliminowane 12 z 15 elementów. Wiemy, że jeśli 19 istnieje w tablicy, to musi istnieć gdzieś pomiędzy elementem Element numer 8 i numer 10. 

Tak więc obliczyć nowy punkt środkowy ponownie. 8 plus 10 jest 18, dzieli się przez 2 9. I w tym przypadku, wygląd, cel jest w środku. Znaleźliśmy dokładnie to, czego szukasz. Mozemy przestac. Z powodzeniem zakończone binarny wyszukiwania. W porządku. Więc wiemy tego algorytmu działa, jeśli cel jest gdzieś w środku tablicy. To działa algorytm jeśli cel nie znajduje się w tablicy? Cóż, zacznijmy go ponownie i tym razem, spójrzmy na elemencie 16, które wizualnie możemy zobaczyć nie występują wszędzie w tablicy. 

Punkt początkowy jest znowu 0. Punkt końcowy jest jeszcze 14. Są to wskaźniki pierwszego i ostatnie elementy kompletnej tablicy. A my przejść przez proces po prostu ponownie przeszedł, starając się znaleźć 16, chociaż wizualnie, już możliwe powiedzieć, że to nie będzie tam być. Chcemy tylko, aby upewnić się, że ten algorytm będzie w rzeczywistości nadal pracują w sposób a nie tylko zostawić nas utknąć w nieskończonej pętli. 

Więc co jest krokiem w pierwszej kolejności? Oblicz punkt środkowy bieżącej tablicy. Co znajduje się punkt środkowy bieżącej tablicy? Cóż, jest to 7, prawda? 14 oraz 0 podzielone przez 2 to 7. Jest 15, co szukasz? Nie. Jest to dość blisko, ale szukamy o wartości nieznacznie większej niż. 

Wiemy, że to będzie mieć nigdzie w lewo 15. Docelowa jest większa niż co jest w punkcie środkowym. I tak ustawić nowy punkt początkowy do się na prawo od środka. Punkt środkowy jest obecnie 7, więc powiedzmy, że nowy punkt początkowy jest 8. A co skutecznie mam wykonane ponownie jest ignorowany cała lewa połowa macierzy. 

Teraz powtórz proces jeszcze raz. Oblicz nowy punkt środkowy. 8 oraz 14 jest 22, dzieli się przez 2 jest 11. Jest 23, co szukasz? Niestety nie. Szukamy wartości która jest mniejsza niż 23. I tak w tym przypadku, będziemy zmienić punkt końcowy, który jest po prostu w lewo bieżącego punktu środkowego. Obecny punkt środkowy jest 11, a więc będziemy ustawić nowy punkt końcowy następnym razem idziemy w tym procesie do 10. 

Ponownie przejść przez proces ponownie. Oblicz punkt środkowy. 8 plus 10 podzielone przez 2 to 9. Jest 19, co szukasz? Niestety nie. Wciąż szukasz wiele mniej. Będziemy więc zmienić punkt końcowy, tym razem się na lewo od punktu środkowego. Punkt środkowy jest obecnie 9, więc punkt końcowy będzie 8. A teraz, po prostu patrząc w jednym elemencie tablicy. 

Co znajduje się punkt środkowy tej tablicy? Cóż, to zaczyna się o 8, to kończy się na 8, punkt środkowy jest 8. Czy to jest to, czego szukasz? Szukamy 17? Nie, szukamy 16. Tak więc, jeżeli istnieje w tablicy musi gdzieś istnieć z lewej strony w którym aktualnie jesteśmy. Więc co zrobimy? Cóż, ustawić punkt końcowy, aby być tylko w lewo bieżącego punktu środkowego. Będziemy więc zmienić punkt końcowy do 7. Czy widzisz, co się tu się stało, chociaż? Spójrz tutaj. 

Start jest teraz większa niż koniec. W efekcie, obydwa końce naszej tablicy są skrzyżowane, i punkt startu Teraz, po punkcie końcowym. Dobrze, że nie żadnego sensu, prawda? Więc teraz, co możemy powiedzieć, to to, że mają sub wachlarz wielkości 0. A kiedy mamy zdobyć się ten punkt, możemy teraz Gwarantujemy ten element 16 nie istnieje w tablicy Ponieważ punkt startu i punkt końcowy przekroczyły. I tak go nie ma. Teraz zwróć uwagę, że jest to nieco różni się od punktu startu i końca punkt znajduje się taka sama. Gdybyśmy byli patrząc na 17, to mają było w tablicy, a punktem startowym i punkt końcowy tej ostatniej iteracji zanim te punkty skrzyżowane, znaleźlibyśmy 17 tam. To tylko wtedy, gdy przekraczają one, że możemy Gwarantujemy, że element nie istnieje w tablicy. 

Warto więc o wiele mniej kroków niż wyszukiwania liniowego. W najgorszym przypadku, mieliśmy podzielić listę n elementów wielokrotnie w połowie, aby znaleźć cel, albo dlatego, że element docelowy będzie gdzieś w ostatni Podział lub nie istnieją w ogóle. Tak więc w najgorszym przypadku, mamy do podzielone na array-- wiesz? Log n razy; my trzeba wyciąć problem w pół pewną liczbę razy. To ile razy jest log n. 

Jaki jest najlepszy scenariusz? Cóż, pierwszy razem obliczyć punkt środkowy, możemy znaleźć to, czego szukamy. W sumie poprzedni przykłady dotyczące wyszukiwania binarnego my właśnie przeszedł, gdybyśmy mieli szukamy elementu 15, nie stwierdzono, że natychmiast. To było na samym początku. To był punkt środkowy pierwsza próba podziału dywizji w poszukiwaniu binarnym. 

I tak w najgorszym Sprawa, wyszukiwania binarnego działa w log n, która jest znacznie lepsza niż poszukiwanie liniowej, w najgorszym przypadku. W najlepszym przypadku, binarny Wyszukiwarka działa w omega 1. Więc przeszukiwanie binarne jest dużo lepiej niż wyszukiwania liniowego, ale masz do czynienia z procesem sortowanie swoją tablicę zanim można wykorzystać możliwości wyszukiwania binarnego. 

Jestem Doug Lloyd. To CS 50.