>> [MUSIC PLAYING]
DOUG LLOYD: Linear Axtarış alqoritm biz
bir sıra bir element tapmaq üçün istifadə edə bilərsiniz.
Bir alqoritm geri bir addım-addım müəyyən edilir
bir vəzifə doldurulması təlimatlar.
>> xətti axtarış Aşağıdakı kimi alqoritm çalışır.
Soldan array arasında təkrarlamaq sağ, müəyyən bir element üçün axtarır.
>> Pseudocode, olan bir çox Bu cümlənin distillə edilmiş versiyası
ilk element, əgər nə Siz dayandıra bilər aradığınız.
Əks halda, növbəti element hərəkət və Siz tapmaq qədər üzərində davam
element, və ya deyil.
Beləliklə, biz xətti istifadə edə bilərsiniz axtarış alqoritmi, məsələn,
hədəf dəyər tapmaq üçün Bu array doqquz.
Yaxşı başında.
Biz istəyirik nə varsa axtarır, biz dayandıra bilər.
Bu, biz 11 axtarır deyilik deyil.
Belə ki, başqa, növbəti element üçün hərəkət.
>> Belə ki, biz 23 oldu.
Biz aradığınız nə 23?
Heç bir yaxşı, belə ki, biz növbəti hərəkət element və növbəti element,
və biz vasitəsilə davam üzərində bu proses
və artıq qədər biz torpaq Bu kimi bir vəziyyət var.
>> Nine, biz aradığınız nə və serialın bu element
, o, dəyəri doqquz edir.
Və belə ki, biz istəyirik nə tapılmadı axtarır və biz dayandıra bilər.
xətti axtarış var müvəffəqiyyətlə başa çatmışdır.
>> Amma biz nə arıyorsanız haqqında bizim array deyil bir element.
Xətti axtarış hələ işləyir?
Yaxşı əmin olun.
Beləliklə, biz bu prosesi təkrar ilk element başlayır.
Biz istəyirik nə varsa axtarır, biz dayandıra bilər.
Bu deyil.
Əks halda, biz növbəti element üçün hərəkət.
>> Lakin biz bu prosesi təkrar edə bilərsiniz Öz növbəsində hər element araşdıraraq,
biz sayı 50 tapmaq ki, ümid.
Amma biz əgər bilmək deyil biz sayı 50 gördük
etmədik və ya biz qədəm etdiyiniz qədər serialın hər bir element üzərində.
>> Yalnız biz etdik dəfə ki, qısa gəlmək
biz ki, bağlaya bilər 50 array deyil.
Və belə xətti axtarış alqoritm, uğursuz yaxşı, özlüyündə.
Amma mənada ki, bu bunu uğursuz oldu nə
biz bunu istədi.
>> Bu da uğursuz oldu Bu 50 tapmadı qədər,
lakin 50 array deyildi.
Amma biz exhaustively axtarış var hər bir element vasitəsilə
və belə ikən biz tapmadı bir şey, xətti axtarış hələ
bacarar, hətta element array deyil.
>> Belə ki, nə ən pis halda var xətti axtarış ssenari?
Yaxşı vasitəsilə baxmaq lazımdır hər bir element,
ya çünki hədəf element serialın son element edir
və ya biz aradığınız element deyil əslində bütün array mövcuddur.
Ən yaxşı ssenari nədir?
Yaxşı tapa bilərsiniz dərhal element.
Və neçə elementləri biz sonra baxmaq var
ən yaxşı halda da, Biz bunun üçün arıyorsanız
və biz çox başında tapa?
Biz dərhal dayandıra bilər.
>> Bu barədə nə deyir xətti axtarış mürəkkəbliyi?
Yaxşı, ən pis halda, biz hər bir element baxmaq.
Və belə bir O çalışır n, ən pis halda.
>> Ən yaxşı halda, biz çalışırıq dərhal element tapa bilərsiniz.
Və belə 1 omega çalışır.
>> Mən Doug Lloyd edirəm.
Bu CS50 edir.