ZAMYLA Чан: Першае, што вы маглі б апавяшчэнне аб знаходцы з'яўляецца тое, што мы ўжо ўжо код, напісаны для нас. Гэта называецца код размеркаванне. Такім чынам, мы не толькі напісанне ўласнай код з нуля больш. Хутчэй, мы запаўнення пустэч у некаторым папярэдне існуючага кода. 

Праграма find.c запытвае нумары запоўніць стог сена, пошук стозе сена для карыстальнікаў прадстаўленых іголкі, і ён робіць гэта шляхам выкліку роду і пошуку, функцыі, пэўныя у helpers.c. Так find.c напісана ўжо. Ваша задача напісаць памочнікаў. 

Так што мы робім? Мы рэалізацыі дзве функцыі. Пошук, які вяртае ісціну, калі значэнне знаходзіцца ў стозе сена, вяртаючыся ілжывым, калі значэнне не ў стозе сена. А потым мы таксама ажыццяўляе сартаванне, якая сартуе масіў з імем значэння. Так што давайце вырашаць пошуку. 

Пошук у цяперашні час рэалізаваны у якасці лінейнага пошуку. Але вы можаце зрабіць нашмат лепш, чым гэта. Лінейны пошук ажыццяўляецца ў O п час, якое з'яўляецца даволі павольным, хоць гэта можаце шукаць любой спіс, дадзенае яму. Ваша задача заключаецца ў рэалізацыі бінарны пошук, які падчас выканання O з часопіса п. Гэта даволі хутка. 

Але ёсць агаворка. Двайковага пошуку можна толькі пошук праз папярэдне парадку п. спісаў. Чаму гэта адбываецца? Што ж, давайце паглядзім на прыкладзе. Улічваючы масіў значэнняў, стог сена, мы збіраемся шукаць іголку, і ў гэтым Напрыклад, цэлы лік 3. 

Такім чынам, што бінарны пошук працуе так, што мы параўнаем сярэдні кошт масіў да іголкі, гэтак жа, як, як мы адкрылі тэлефонную кнігу да сярэдзіны старонкі ў тыдзень 0. Такім чынам, пасля параўнання сярэдняе значэнне для іголка, вы можаце адмовіцца ад альбо налева або правая палова масіва зацягнуўшы свае межы. У гэтым выпадку, паколькі 3, наша іголка, з'яўляецца менш за 10, сярэдняе значэнне, Права мяжа можа змяншацца. 

Але паспрабаваць зрабіць вашыя мяжы як мага шчыльней. Калі сярэдняе значэнне не іголка, то вы ведаеце, што вам не трэба, каб ўключыць яго ў гэтай катэгорыі. Так ваша права звязаны можа зацягнуць пошук мяжы ледзь-ледзь больш, ня і гэтак далей і гэтак далей, да тых часоў, вы знайшлі іголку. 

Такім чынам, што ж псеўда Код выглядае? Ну, у той час як мы ўсё яшчэ праглядаючы спіс і да гэтага часу элементы, каб глядзець у, мы бярэм сярэдзіну з спісу і параўнаць, што сярэдняе значэнне для нашай іголкі. Калі яны роўныя, то гэта азначае, што мы ў знайшла іголку, і мы можам вярнуцца дакладна. 

У адваротным выпадку, калі іголка менш сярэдняе значэнне, тое, што азначае, што мы можна адкінуць правую палову і проста пошук па левы бок масіва. У адваротным выпадку, мы будзем шукаць Правая частка масіва. І ў канцы, калі вы не маеце любыя больш элементаў злева пошук, але вы Нічога не знайшлі іголку яшчэ, то вы вярнуцца ілжывым. Паколькі іголка вызначана не ў сена. 

Цяпер адзін акуратны рэч пра гэта псеўда код у бінарны пошук у тым, што ён можа інтэрпрэтавацца як альбо итеративный або рэкурсіўная рэалізацыя. Таму было б рэкурсіўным, калі вы назвалі функцыя пошуку ў пошуку функцыянаваць па абодва паловы масіва. Мы разгледзім рэкурсіі трохі пазней у ходзе. Але дакладна ведаю, што гэта варыянт калі вы хацелі б паспрабаваць.