>> ZAMYLA Chan: Siz bilər ilk şey tapmaq haqqında xəbərdarlıq edir ki, biz artıq
kodu bizim üçün yazıblar.
Bu distribution kodu adlanır.
Beləliklə, biz yalnız öz yazılı deyilik artıq sıfırdan kodu.
Əksinə, biz boşluqları dolduraraq edirik bəzi pre-mövcud kodu.
>> The find.c proqram nömrələri üçün tələb Bu ot tayası doldurmaq üçün axtarış
bir istifadəçi təqdim iynə ot tayası, və bu cür zəng və bu yoxdur
axtarış, funksiyaları müəyyən helpers.c da.
Belə ki, find.c artıq yazılmışdır.
Sizin iş köməkçiləri yazmaq üçün.
>> Beləliklə, biz nə edirik?
Biz iki funksiyaları həyata edirik.
Doğru qayıdır axtarış, əgər bir dəyər qaytarılması, ot tayası aşkar
yalan dəyəri əgər deyil ot tayası.
Və sonra biz də sort həyata edirik, olan dəyərlər adlı array növ.
Belə ki, axtarış həll edək.
>> Axtarış hazırda həyata keçirilir xətti axtarış kimi.
Amma siz ki, daha yaxşı edə bilərsiniz.
Xətti axtarış n O həyata keçirilir olduqca yavaş olan zaman, bu, baxmayaraq
ona verilmiş hər hansı siyahısı axtarış edə bilərsiniz.
Sizin iş ikili axtarış həyata keçirmək, log n vaxt O davam edən.
Bu olduqca sürətli.
>> Amma bir şərt var.
Binary axtarış yalnız axtarış edə bilərsiniz pre-sıralanır siyahıları vasitəsilə.
Niyə ki?
Yaxşı, bir misal baxaq.
Dəyərlərin bir sıra nəzərə alaraq, ot tayası, biz axtarır olacaq
bir iynə, və bu Məsələn, tam 3.
>> Ikili axtarış çalışır ki, yol ki, biz orta dəyəri müqayisə
çox kimi iynə üçün array, necə biz ortada bir telefon kitab açdı
Həftə 0 səhifə.
Belə ki, üçün orta dəyər müqayisə sonra iynə, ya imtina edə bilər
sol və ya serialın sağ yarım Sizin həddi daralma ilə.
Bu halda, 3 ildən, bizim iynə edir az 10, orta dəyəri,
sağ bound azalda bilər.
>> Lakin həddi etmək üçün cəhd mümkün qədər sıx.
Orta dəyəri iynə deyilsə, sonra sizə lazım deyil ki, bilirik
axtarış daxil.
Belə ki, bağlı sağ bərkidin bilər yalnız kiçik bir bit daha search həddi,
və s və s qədər Siz iynə tapa bilərsiniz.
>> Belə ki, yalançı nə edir kodu kimi baxmaq?
Bəli, biz hələ də axtarır etdiyiniz zaman siyahısı və hələ də
baxmaq elementləri, biz ortasında almaq siyahısı və müqayisə
Bizim iynə orta dəyəri.
Onlar bərabər etdiyiniz, onda ki, biz var deməkdir iynə gördük və biz
doğru geri.
>> Əks halda, iynə az olduqda orta dəyəri, sonra ki, biz deməkdir
yalnız sağ yarım imtina edə bilər serialın sol axtarış.
Əks halda, biz axtarış lazımdır Serialın sağ.
Və sonunda, əgər hər hansı bir yoxdur daha axtarmaq üçün sol elementləri ancaq
hələ iynə tapılmadı, sonra saxta qayıtmaq.
Iynə mütləq, çünki ot tayası deyil.
>> İndi, bu yalançı bir səliqəli şey ikili axtarış kodu bilər ki
bir iterative ya kimi təfsir edilə və ya recursive həyata keçirilməsi.
Adlı əgər Belə ki, recursive olacaq Axtarış ərzində axtarış funksiyası
Serialın ya yarısında fəaliyyət göstərir.
Biz recursion bir az əhatə edəcəyik sonra kurs.
Amma bu bir seçim olduğunu bilmirəm Siz cəhd istəyirsinizsə.