>> 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.