ROB BOWDEN: Cześć, jestem Rob. Jak zatrudniamy binarnego wyszukiwania? Przekonajmy się. Tak więc należy pamiętać, że to wyszukiwanie jedziemy wdrożyć rekurencyjnie. Można też zaimplementować wyszukiwanie binarne iteracyjnie, więc jeśli to zrobił, to jest całkowicie w porządku. 

Teraz pierwsze, pamiętajmy, co parametry wyszukiwania mają być. Tutaj widzimy wartość int, który jest powinna być wartość użytkownika poszukiwania. Widzimy tablicę wartości int, które jest tablicą, w której jesteśmy poszukiwanie wartości. I widzimy, int n, która jest Długość naszego układu. 

Teraz pierwsza rzecz pierwsza. Sprawdzamy, czy n jest równe 0, w takim przypadku zwracamy false. To tylko, że jeśli mamy pusty tablica, wartość wyraźnie nie jest w pusta tablica, więc możemy wrócić fałszywe. 

Teraz, tak naprawdę chcą zrobić binarne szukaj częścią poszukiwania binarnego. Tak, chcemy znaleźć w środku Element tej tablicy. Tutaj mówimy, jest równa n dzieli średnim od 2, gdyż Element środkowy jest Będzie długość Nasza tablica podzielić przez 2. Teraz mamy zamiar sprawdzić, czy środkowy element jest równa wartości jesteśmy poszukiwania. Tak więc, jeśli wartość jest równa wartości środkowe, my może wrócić prawda od znaleźliśmy wartość w naszej tablicy. 

Ale jeśli to nie była prawda, teraz musimy zrobić rekurencyjnego etap poszukiwania binarnego. Musimy sprawdzić czy do z lewej strony macierzy lub Środek tablicy. Więc tutaj mówimy, jeśli w środku jest wartości mniejsza niż wartość, oznacza to, że wartość jest większa niż w połowie tablicy. Więc wartość musi być po prawej element, który po prostu spojrzał na. 

Więc tutaj, będziemy szukaj rekurencyjnie. I będziemy patrzeć na to, co przekazujemy W tym celu na sekundę. Ale będziemy szukać do na prawo od elementu środkowego. I w drugim przypadku oznacza to, że wartość była mniejsza niż w połowie tablicy, i tak będziemy szukać w lewo. Teraz lewa będzie nieco łatwiejsze do zobaczenia. Tak więc, widzimy, że jesteśmy rekurencyjnie dzwoniąc wyszukiwanie gdzie pierwszy argument jest, ponownie, wartość patrzymy na. Drugi argument ma być Tablica szukaliśmy ponad. I ostatni element jest środkowy. Zapamiętaj ostatni parametr jest nasz int n, więc to długość naszej tablicy. 

W zaproszeniu do wyszukiwania rekurencyjnego jesteśmy teraz mówi, że długość Tablica jest środkowy. Tak więc, jeśli nasza tablica była wielkości 20 i my Wyszukiwanie w indeksie 10, ponieważ jest środkowa 20 podzielone przez 2, co oznacza, że ​​jesteśmy przechodząc 10 jako nowe długość naszej tablicy. Pamiętaj, że gdy masz tablicę o długości 10, co oznacza, że ​​ważne elementy są w indeksach 0 do 9. Tak, to jest dokładnie to, co chcemy określić naszą zaktualizowaną tablicę - lewy tablicy od elementu środkowego. 

Tak więc, patrząc na prawo jest nieco trudniejsze. Teraz pierwsze, rozważmy długość tablicy z prawej Element środkowy. Tak więc, jeśli nasza tablica był wielkości n, to Nowa tablica będzie rozmiar n minus Bliski minus 1. Więc pomyślmy n minus środku. 

Ponownie, jeśli tablica miały wielkość 20 i podzielić przez 2, aby uzyskać środek, tak środkowy jest 10, to n minus środkowy ma dać nam 10, więc 10 Elementy z prawej połowie. Ale mamy też ten minus 1, ponieważ nie chcemy, aby m.in. samego pola. Więc n minus środkowa minus 1 daje nam liczba elementów do prawej środkowej indeksu tablicy. 

Teraz tutaj, pamiętaj, że w średnim parametrem jest tablica wartości. Więc tutaj, przekazujemy aktualizowana tablica wartości. Te wartości dodatnie oraz 1 jest średnim właściwie mówiąc rekursywnie wywołać wyszukiwanie, przechodząc w nowej tablicy, gdzie że nowa tablica zaczyna się w środku plus jeden z naszych oryginalnych wartości tablicy. 

Alternatywna składnia, że ​​teraz, zacząłeś widzieć wskaźniki, jest Ampersand średnim oraz wartości 1. Więc chwyć adres środku plus jeden element wartości. 

Teraz, jeśli nie były wygodne modyfikując tablicę takiego, jesteś mógł również realizowane za pomocą tego rekurencyjna funkcja pomocnika, gdzie że funkcja pomocnika trwa więcej argumentów. Więc zamiast brać tylko wartość, tablica i rozmiar tablicy Funkcja pomocnika może zająć więcej argumenty, tym niższy wskaźnik że Ci zależy w tablicy i górny indeks, który obchodzi o tablicy. 

I tak śledzenia zarówno dolna indeks górny i indeks, nie musisz trzeba zawsze zmienić oryginalne wartości tablicy. Możesz po prostu nadal korzystać z tablicy wartości. Ale tutaj zauważyć, że nie potrzebujemy pomocnika działać tak długo, jak jesteśmy gotów zmodyfikować oryginalny Wartości tablicy. Jesteśmy gotowi przekazać w zaktualizowanej wartości. 

Teraz nie możemy binarnego wyszukiwania nad Tablica jest nieposortowane. Więc miejmy to załatwione. Teraz zauważył, że sortowanie jest przeszłość dwa Parametry int wartości, co jest Tablica mamy sortowanie i int n, która jest długością tablicy, która my sortowania. Tak, tu chcemy realizować Algorytm sortowania że jest o n do kwadratu. Można wybrać sortowanie bąbelkowe, wybór sortowania lub wstawiania sortowania, lub inny rodzaj nie mamy widoczne w klasie. Ale tu, będziemy korzystać wyboru Sortuj. 

Tak, jedziemy do iteracji całego układu. Cóż, tutaj widzimy, że mamy do iteracji od 0 do n minus 1. Dlaczego nie wszyscy aż do n? Cóż, jeśli mamy już posortowane pierwszy n minus 1, to elementy Ostatnim elementem tego, co musi być już w odpowiednim miejscu, tak sortowania na cała tablica. 

Teraz pamiętam, jak wybór sortowania działa. Zamierzamy przejść całego układu patrząc na wartości minimalnej i kij, że tablica na początku. Wtedy będziemy iść na całego tablica znowu patrząc na sekundę najmniejszy element, i trzymać się, że na drugiej pozycji w tablica i tak dalej. Tak, to co to robi. 

Tutaj widzimy, że jesteśmy Ustawienie aktualnego minimum wartość indeksu i-tego. Więc w pierwszej iteracji, jedziemy do rozważenia jest minimalna wartość Początek naszej tablicy. Następnie jedziemy do iteracyjnego Pozostała część układu, w celu sprawdzenia sprawdzić, czy wszystkie elementy mniejsze niż jeden, że jesteśmy obecnie biorąc pod uwagę minimum. 

Więc tutaj, wartości j plus jeden - to jest mniej niż to, co mamy obecnie biorąc pod uwagę minimum. Wtedy będziemy aktualizować co uważamy, że jest minimalna Indeks j oraz 1. Tak, to, że na całej tablicy, i po to minimum dla pętli, powinna być minimalna od elementu Pozycja I-go w tablicy. 

Kiedy już mamy, możemy zamienić Minimalna wartość na i-tej pozycji w tablicy. Więc jest to tylko zwykła zamiana. Przechowujemy w wartości czasowej - wartość i-tego w tablicy - umieścić w i-tej wartości w tablicy Minimalna wartość, jaką należy tam, , a następnie z powrotem do przechowywania, gdzie Obecna wartość minimalna dawniej i-wartość w tablicy, tak że nie straci go. 

Tak, że w dalszym ciągu na kolejnej iteracji. Zaczniemy patrząc na sekundę Minimalna wartość i wstawić, że do druga pozycja. Na trzeciej iteracji, będziemy szukać Trzecia wartość minimalna i wkładka że w trzecim położeniu, a więc dopóki mamy posortowaną tablicę. Nazywam się Rob, i to był wybór sortowania.