1
00:00:00,000 --> 00:00:02,892
>> [MUSIC nagpe-play]

2
00:00:02,892 --> 00:00:05,347

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: De
search ay isang algorithm namin

4
00:00:07,180 --> 00:00:09,840
ay maaaring gamitin upang mahanap ang isang elemento sa isang array.

5
00:00:09,840 --> 00:00:11,990
Isang algorithm recall
ay isang step-by-step na set

6
00:00:11,990 --> 00:00:15,030
ng mga tagubilin para sa pagkumpleto ng isang gawain.

7
00:00:15,030 --> 00:00:17,480
>> Ang haba ng paghahanap
algorithm ay gumagana tulad ng sumusunod.

8
00:00:17,480 --> 00:00:22,200
Ulitin sa buong array mula kaliwa
karapatan, naghahanap para sa isang tinukoy na elemento.

9
00:00:22,200 --> 00:00:26,380
>> Sa pseudocode, na kung saan ay isang mas
dalisay na bersyon ng pangungusap na ito,

10
00:00:26,380 --> 00:00:29,840
kung ang unang elemento ay kung ano ang
naghahanap ka ng, maaari mong itigil.

11
00:00:29,840 --> 00:00:33,930
Kung hindi man, ilipat sa susunod na elemento at
panatilihin ang pagpunta nang paulit-ulit hanggang sa mahanap mo

12
00:00:33,930 --> 00:00:36,389
ang elemento, o hindi mo gusto.

13
00:00:36,389 --> 00:00:38,680
Kaya maaari naming gamitin ang mga linear
algorithm sa paghahanap, halimbawa,

14
00:00:38,680 --> 00:00:42,330
upang mahanap ang target na halaga
siyam na sa array na ito.

15
00:00:42,330 --> 00:00:43,870
Well simulan natin sa simula.

16
00:00:43,870 --> 00:00:45,970
Kung ito ay kung ano ang hindi namin
naghahanap para sa, maaari naming ihinto.

17
00:00:45,970 --> 00:00:47,890
Ito ay hindi, kami ay hindi naghahanap para sa 11.

18
00:00:47,890 --> 00:00:50,220
Kaya sa kabilang banda, lumipat sa susunod na elemento.

19
00:00:50,220 --> 00:00:51,510
>> Kaya tayo ay tumingin sa 23.

20
00:00:51,510 --> 00:00:52,730
Ay 23 kung ano ang namin ang iyong hinahanap?

21
00:00:52,730 --> 00:00:55,614
Well no, kaya lumipat kami sa mga susunod na
elemento, at ang susunod na sangkap,

22
00:00:55,614 --> 00:00:57,780
at panatilihin namin ang pagpunta sa pamamagitan ng
ang proseso na ito nang paulit-ulit

23
00:00:57,780 --> 00:01:01,030
at higit sa, hanggang sa makarating kami
sa isang sitwasyon na ito.

24
00:01:01,030 --> 00:01:03,910
>> Siyam ay kung ano ang aming hinahanap,
at ito elemento ng array

25
00:01:03,910 --> 00:01:05,787
ay, ang halaga na ito ay siyam.

26
00:01:05,787 --> 00:01:08,120
At kaya nakita namin kung ano kami
naghahanap para sa, at maaari naming ihinto.

27
00:01:08,120 --> 00:01:11,910
Ang haba ng paghahanap ay may
Matagumpay na natapos,.

28
00:01:11,910 --> 00:01:15,370
>> Ngunit ano ang tungkol sa kung kaming naghahanap ng mga
isang elemento na hindi sa aming array.

29
00:01:15,370 --> 00:01:17,040
Ba linear search pa rin gumagana?

30
00:01:17,040 --> 00:01:17,540
Well sigurado.

31
00:01:17,540 --> 00:01:19,947
Kaya ulitin namin ang proseso na ito
simula sa unang elemento.

32
00:01:19,947 --> 00:01:21,780
Kung ito ay kung ano ang hindi namin
naghahanap para sa, maaari naming ihinto.

33
00:01:21,780 --> 00:01:22,800
Hindi.

34
00:01:22,800 --> 00:01:25,020
Kung hindi man, ilipat namin sa susunod na elemento.

35
00:01:25,020 --> 00:01:29,050
>> Ngunit maaari naming patuloy na paulit-ulit ang proseso na ito,
pagsusuri sa bawat elemento sa turn,

36
00:01:29,050 --> 00:01:31,720
umaasa na mahanap namin ang bilang 50.

37
00:01:31,720 --> 00:01:33,750
Ngunit hindi namin alam kung
nalaman namin ang bilang 50

38
00:01:33,750 --> 00:01:38,290
o kung hindi namin ginawa, hanggang sa na namin stepped
sa paglipas ng bawat solong elemento ng array.

39
00:01:38,290 --> 00:01:40,440
>> Isang beses lamang ang aming nagawa
na iyon at lumapit maikli,

40
00:01:40,440 --> 00:01:43,040
maaari naming tapusin na
50 ay wala sa array.

41
00:01:43,040 --> 00:01:46,410
At upang ang mga linear paghahanap
algorithm, well ito ay nabigo, per se.

42
00:01:46,410 --> 00:01:49,181
Ngunit hindi sa kamalayan na ito
Hindi naging matagumpay sa paggawa ng kung ano

43
00:01:49,181 --> 00:01:49,930
tinanong namin ito upang gawin.

44
00:01:49,930 --> 00:01:52,390
>> Ito ay hindi matagumpay sa bilang
mas maraming bilang hindi ito mahanap ang 50,

45
00:01:52,390 --> 00:01:54,070
ngunit 50 ay wala sa array.

46
00:01:54,070 --> 00:01:57,310
Ngunit exhaustively namin ang naghanap
sa pamamagitan ng bawat solong elemento

47
00:01:57,310 --> 00:02:00,550
at sa gayon, habang kami ay hindi mahanap
kahit ano, sa haba ng paghahanap pa rin

48
00:02:00,550 --> 00:02:05,230
magtagumpay kahit na ang
element ay hindi sa array.

49
00:02:05,230 --> 00:02:07,507
>> Kaya kung ano ang pinakamasama kaso
senaryo sa linear paghahanap?

50
00:02:07,507 --> 00:02:09,590
Well mayroon kaming upang tumingin sa pamamagitan ng
bawat solong elemento,

51
00:02:09,590 --> 00:02:14,590
alinman dahil ang target element
ay ang huling elemento ng array,

52
00:02:14,590 --> 00:02:18,510
o ang elemento kaming naghahanap ng mga hindi
ang tunay na umiiral sa array sa lahat.

53
00:02:18,510 --> 00:02:19,760
Ano ang pinakamahusay na kaso sitwasyon?

54
00:02:19,760 --> 00:02:22,430
Well baka makita natin ang
element agad.

55
00:02:22,430 --> 00:02:24,360
At kung gaano karaming mga elemento
huwag pagkatapos kami ay may sa hitsura

56
00:02:24,360 --> 00:02:26,859
sa sa pinakamahusay na kaso,
kung kami ay naghahanap para sa mga ito

57
00:02:26,859 --> 00:02:28,400
at nakita namin ito sa pinakadulo simula?

58
00:02:28,400 --> 00:02:29,850
Maaari naming ihinto agad.

59
00:02:29,850 --> 00:02:32,984
>> Ano ang ibig sabihin tungkol sa
kumplikado ng linear paghahanap?

60
00:02:32,984 --> 00:02:35,650
Well sa pinakamasama kaso, kami ay
upang tumingin sa bawat solong elemento.

61
00:02:35,650 --> 00:02:38,930
At sa gayon ito ay tumatakbo sa O ng
n, sa pinakamasama kaso.

62
00:02:38,930 --> 00:02:41,540
>> Sa pinakamahusay na kaso, hindi namin gonna
mahanap agad ang element.

63
00:02:41,540 --> 00:02:44,750
At kaya ay tumatakbo sa wakas ng 1.

64
00:02:44,750 --> 00:02:45,780
>> Ako Doug Lloyd.

65
00:02:45,780 --> 00:02:48,020
Ito ay CS50.

66
00:02:48,020 --> 00:02:49,876