1 00:00:00,000 --> 00:00:02,892 >> [MUSIC PLAYING] 2 00:00:02,892 --> 00:00:05,347 3 00:00:05,347 --> 00:00:07,180 DOUG LLOYD: Linear Axtarış alqoritm biz 4 00:00:07,180 --> 00:00:09,840 bir sıra bir element tapmaq üçün istifadə edə bilərsiniz. 5 00:00:09,840 --> 00:00:11,990 Bir alqoritm geri bir addım-addım müəyyən edilir 6 00:00:11,990 --> 00:00:15,030 bir vəzifə doldurulması təlimatlar. 7 00:00:15,030 --> 00:00:17,480 >> xətti axtarış Aşağıdakı kimi alqoritm çalışır. 8 00:00:17,480 --> 00:00:22,200 Soldan array arasında təkrarlamaq sağ, müəyyən bir element üçün axtarır. 9 00:00:22,200 --> 00:00:26,380 >> Pseudocode, olan bir çox Bu cümlənin distillə edilmiş versiyası 10 00:00:26,380 --> 00:00:29,840 ilk element, əgər nə Siz dayandıra bilər aradığınız. 11 00:00:29,840 --> 00:00:33,930 Əks halda, növbəti element hərəkət və Siz tapmaq qədər üzərində davam 12 00:00:33,930 --> 00:00:36,389 element, və ya deyil. 13 00:00:36,389 --> 00:00:38,680 Beləliklə, biz xətti istifadə edə bilərsiniz axtarış alqoritmi, məsələn, 14 00:00:38,680 --> 00:00:42,330 hədəf dəyər tapmaq üçün Bu array doqquz. 15 00:00:42,330 --> 00:00:43,870 Yaxşı başında. 16 00:00:43,870 --> 00:00:45,970 Biz istəyirik nə varsa axtarır, biz dayandıra bilər. 17 00:00:45,970 --> 00:00:47,890 Bu, biz 11 axtarır deyilik deyil. 18 00:00:47,890 --> 00:00:50,220 Belə ki, başqa, növbəti element üçün hərəkət. 19 00:00:50,220 --> 00:00:51,510 >> Belə ki, biz 23 oldu. 20 00:00:51,510 --> 00:00:52,730 Biz aradığınız nə 23? 21 00:00:52,730 --> 00:00:55,614 Heç bir yaxşı, belə ki, biz növbəti hərəkət element və növbəti element, 22 00:00:55,614 --> 00:00:57,780 və biz vasitəsilə davam üzərində bu proses 23 00:00:57,780 --> 00:01:01,030 və artıq qədər biz torpaq Bu kimi bir vəziyyət var. 24 00:01:01,030 --> 00:01:03,910 >> Nine, biz aradığınız nə və serialın bu element 25 00:01:03,910 --> 00:01:05,787 , o, dəyəri doqquz edir. 26 00:01:05,787 --> 00:01:08,120 Və belə ki, biz istəyirik nə tapılmadı axtarır və biz dayandıra bilər. 27 00:01:08,120 --> 00:01:11,910 xətti axtarış var müvəffəqiyyətlə başa çatmışdır. 28 00:01:11,910 --> 00:01:15,370 >> Amma biz nə arıyorsanız haqqında bizim array deyil bir element. 29 00:01:15,370 --> 00:01:17,040 Xətti axtarış hələ işləyir? 30 00:01:17,040 --> 00:01:17,540 Yaxşı əmin olun. 31 00:01:17,540 --> 00:01:19,947 Beləliklə, biz bu prosesi təkrar ilk element başlayır. 32 00:01:19,947 --> 00:01:21,780 Biz istəyirik nə varsa axtarır, biz dayandıra bilər. 33 00:01:21,780 --> 00:01:22,800 Bu deyil. 34 00:01:22,800 --> 00:01:25,020 Əks halda, biz növbəti element üçün hərəkət. 35 00:01:25,020 --> 00:01:29,050 >> Lakin biz bu prosesi təkrar edə bilərsiniz Öz növbəsində hər element araşdıraraq, 36 00:01:29,050 --> 00:01:31,720 biz sayı 50 tapmaq ki, ümid. 37 00:01:31,720 --> 00:01:33,750 Amma biz əgər bilmək deyil biz sayı 50 gördük 38 00:01:33,750 --> 00:01:38,290 etmədik və ya biz qədəm etdiyiniz qədər serialın hər bir element üzərində. 39 00:01:38,290 --> 00:01:40,440 >> Yalnız biz etdik dəfə ki, qısa gəlmək 40 00:01:40,440 --> 00:01:43,040 biz ki, bağlaya bilər 50 array deyil. 41 00:01:43,040 --> 00:01:46,410 Və belə xətti axtarış alqoritm, uğursuz yaxşı, özlüyündə. 42 00:01:46,410 --> 00:01:49,181 Amma mənada ki, bu bunu uğursuz oldu nə 43 00:01:49,181 --> 00:01:49,930 biz bunu istədi. 44 00:01:49,930 --> 00:01:52,390 >> Bu da uğursuz oldu Bu 50 tapmadı qədər, 45 00:01:52,390 --> 00:01:54,070 lakin 50 array deyildi. 46 00:01:54,070 --> 00:01:57,310 Amma biz exhaustively axtarış var hər bir element vasitəsilə 47 00:01:57,310 --> 00:02:00,550 və belə ikən biz tapmadı bir şey, xətti axtarış hələ 48 00:02:00,550 --> 00:02:05,230 bacarar, hətta element array deyil. 49 00:02:05,230 --> 00:02:07,507 >> Belə ki, nə ən pis halda var xətti axtarış ssenari? 50 00:02:07,507 --> 00:02:09,590 Yaxşı vasitəsilə baxmaq lazımdır hər bir element, 51 00:02:09,590 --> 00:02:14,590 ya çünki hədəf element serialın son element edir 52 00:02:14,590 --> 00:02:18,510 və ya biz aradığınız element deyil əslində bütün array mövcuddur. 53 00:02:18,510 --> 00:02:19,760 Ən yaxşı ssenari nədir? 54 00:02:19,760 --> 00:02:22,430 Yaxşı tapa bilərsiniz dərhal element. 55 00:02:22,430 --> 00:02:24,360 Və neçə elementləri biz sonra baxmaq var 56 00:02:24,360 --> 00:02:26,859 ən yaxşı halda da, Biz bunun üçün arıyorsanız 57 00:02:26,859 --> 00:02:28,400 və biz çox başında tapa? 58 00:02:28,400 --> 00:02:29,850 Biz dərhal dayandıra bilər. 59 00:02:29,850 --> 00:02:32,984 >> Bu barədə nə deyir xətti axtarış mürəkkəbliyi? 60 00:02:32,984 --> 00:02:35,650 Yaxşı, ən pis halda, biz hər bir element baxmaq. 61 00:02:35,650 --> 00:02:38,930 Və belə bir O çalışır n, ən pis halda. 62 00:02:38,930 --> 00:02:41,540 >> Ən yaxşı halda, biz çalışırıq dərhal element tapa bilərsiniz. 63 00:02:41,540 --> 00:02:44,750 Və belə 1 omega çalışır. 64 00:02:44,750 --> 00:02:45,780 >> Mən Doug Lloyd edirəm. 65 00:02:45,780 --> 00:02:48,020 Bu CS50 edir. 66 00:02:48,020 --> 00:02:49,876