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