>> 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 aktualnie realizowany jako poszukiwanie liniowej.
Ale można to zrobić znacznie lepiej.
Szukaj liniowy realizowany jest w O n czas, który jest dość wolny, chociaż
może sprawdzić każdą listę nadane mu.
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?
Cóż, spójrzmy na przykład.
Biorąc pod uwagę, tablica wartości, stóg siana, będziemy szukać
igły, w tym Na przykład, liczba całkowita 3.
>> 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 0.
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ż 3 nasz igła jest mniej niż 10, wartość środkowa,
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.
Więc prawo związane mogą dokręcić wyszukiwania granice tylko trochę więcej,
i tak dalej, i tak dalej, aż Ci znaleźć igłę.
>> Więc co robi pseudo Kod wygląda?
Dobrze, a my wciąż patrząc przez lista i jeszcze
elementy szukać w bierzemy środek z listy i porównać, które
Wartość środkowa naszej igły.
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ę i 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łę, następnie return false.
Bo na pewno igły nie ma w stogu siana.
>> Teraz, jeden schludny rzeczą w tym pseudo Kod w poszukiwaniu binarnego jest to, że można
należy 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 trochę rekurencji później w trakcie.
Ale wiem, że jest to opcja jeśli chcesz spróbować.