[MUZYKA GRA] 

ZAMYLA Chandler: Pierwszą rzeczą, którą może Zawiadomienie o znalezisku jest to, że już Kod napisany nie dla nas. Jest to tak zwany kod dystrybucji. Więc nie tylko pisanie własne kod od zera już. Raczej jesteśmy wypełniania pustek w pewnym uprzednio istniejącym kodzie. 

Program find.c monituje o numerach wypełnić stóg siana, wyszukiwania stóg siana w igle składane przez użytkownika, i robi to przez wywołanie rodzaju i wyszukiwania, funkcje zdefiniowane w helpers.c. Więc find.c napisano już. Twoim zadaniem jest napisać pomocników. 

Więc co robimy? Jesteśmy realizacji dwóch funkcji. Wyszukiwarka, która zwraca true, jeśli wartość znajduje się w stogu siana, wracając false, jeśli wartość jest nie w stogu siana. A potem mamy również realizację rodzaju które sortuje tablicę o nazwie wartości. 

Zajmijmy się więc poszukiwania. Wyszukiwanie jest obecnie realizowany jako Wyszukiwanie liniowe, ale można to zrobić o wiele lepiej. Szukaj liniowy realizowany jest w O czasu n, które jest dość powolna. Chociaż, może to sprawdzić każda lista podana do niego. Twoim zadaniem jest wdrożenie wyszukiwanie binarne, które prowadzi razem Ö log n.. To dość szybko. 

Ale jest warunek. Binary wyszukiwania może wyłącznie przez wstępnie posortowanych list. Dlaczego tak jest? 

No spójrzmy na przykład. Biorąc pod uwagę, tablica wartości, stóg siana, będziemy szukać igły. I w tym przypadku, całkowitą trzy. Sposób, że wyszukiwarka działa jest to, że binarny Porównując wartość środku Tablica z igłą, tak jak jak otworzyliśmy książkę telefoniczną na środku strona w tygodniu zerowym. 

Więc po porównaniu wartości środku igły, można odrzucić albo w lewo lub w prawo pół tablicy dokręcając swoje granice. W tym przypadku, ponieważ trzy nasze igła jest mniejsza niż 10, to wartość środkowy prawo związane może zmniejszyć. Ale spróbuj zrobić swoje granice tak mocno, jak to możliwe. Jeśli wartość środkowa nie jest igła, to wiesz, że nie musisz się umieścić go w wyszukiwaniu. Tak masz rację związany może dokręcić wyszukiwania granice tylko trochę więcej, i tak dalej, i tak dalej, aż Ci znaleźć igłę. 

Więc co pseudokod wygląda? Cóż, gdy my wciąż patrząc przez lista i jeszcze elementy do spojrzeć w, bierzemy na środku listy, i porównać tę wartość do środkowego nasza igła. Jeśli są równe, to znaczy mamy znaleźć igłę i możemy return true. 

W przeciwnym razie, jeśli igła jest mniejsza niż wartość środkowa, to znaczy, że może odrzucić prawą połowę, a tylko szukaj po lewej stronie tablicy. W przeciwnym razie będziemy szukać prawej stronie tablicy. I na koniec, jeśli nie ma żadnych więcej elementów lewo, ale można szukać nie znalazłem swoją igłę jeszcze, to return false, ponieważ igły na pewno nie jest w stogu siana. 

Teraz miłe rzeczy na temat tego Pseudokod w poszukiwaniu binarnym, który może być interpretować albo jako iteracyjny lub rekurencyjna realizacja. Więc byłoby rekurencyjny jeśli nazywa Funkcja wyszukiwania w poszukiwaniu funkcjonować na każdej połowie tej tablicy. Omówimy rekursji nieco później w Oczywiście, ale wiem, że jest to opcję, jeśli chcesz, aby spróbować. 

Teraz spójrzmy na sortowanie. Sortuj pobiera tablicę i całkowitą n, która jest rozmiar tablicy. Teraz są różne rodzaje od rodzaju i można spojrzeć na niektóre spodenki dla dema i objaśnienia. Powrót do naszego typu Funkcja sortowania jest nieaktualna. Więc to oznacza, że ​​nie będziemy powrót żadnej tablicy z rodzaju. Jesteśmy rzeczywiście będzie zmienić bardzo Tablica została przekazana do nas. 

I to jest możliwe, ponieważ tablice są przekazywane przez referencję w C, teraz będziemy zobacz więcej o tym później, ale Zasadnicza różnica między biegiem w coś takiego jak liczba całkowita i przemijania w tablicy, jest to, że kiedy przekazać w postaci liczby całkowitej, C jest po prostu będzie zrobić kopię tej liczby całkowitej i przekazać jej funkcji. Zmienna oryginalna nie zostanie zmieniony po zakończeniu funkcji. Z tablicy, z drugiej strony, jest nie zamierza wykonać kopię, a będziesz faktycznie edycji bardzo sama tablica. 

Więc jeden rodzaj sortowanie jest Sortuj wybór. Wybór sortowania zaczynają się prace początek, a następnie iteracyjne nad i znaleźć najmniejszy element. A następnie zamienić, że najmniejsza Element z pierwszym. A następnie przejść do drugiego elementu , Znaleźć następna najmniejsza Element, a następnie zamienić, że z Drugi element macierzy, ponieważ Pierwszy element jest już posortowana. I tak to nadal dla każdego elementem identyfikacji najmniejsza wartości i zamiana go. 

Bo jest równa 0, pierwszy element, n minus 1, masz zamiar porównać każda następna wartość po tym i znaleźć Wskaźnik wartości minimalnej. Po znalezieniu indeksu wartości minimalnej, można zamienić tę wartość z tablicy Minimalna i tablicy I. 

Innym rodzajem rodzaju, że można wdrożenia jest sortowanie bąbelkowe. Tak iteracje bańka na listę sortowania porównywanie sąsiednich elementów i ciężkich elementów, które są w złej kolejności. I w ten sposób największy elementem będzie bańka do końca. A lista jest posortowana po nie więcej elementy zostały zamienione. 

To są dwa przykłady rodzaju algorytmy, które można wdrożyć do Program find. Po zakończeniu sortowania, a ty wykonane wyszukiwanie, skończysz. Nazywam się Zamyla, i to jest CS50. 

[MUZYKA GRA]