1
00:00:00,000 --> 00:00:02,892
>> [השמעת מוסיקה]

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

3
00:00:05,347 --> 00:00:07,180
דאג LLOYD: בשכבות
חיפוש הוא שאלגוריתם

4
00:00:07,180 --> 00:00:09,840
ניתן להשתמש כדי למצוא אלמנט במערך.

5
00:00:09,840 --> 00:00:11,990
זוכר אלגוריתם
היא קבוצת צעד-אחר-צעד

6
00:00:11,990 --> 00:00:15,030
הוראות להשלמת משימה.

7
00:00:15,030 --> 00:00:17,480
>> החיפוש ליניארי
אלגוריתם פועל באופן הבא.

8
00:00:17,480 --> 00:00:22,200
לחזר פני המערך משמאל ל
נכון, מחפש אלמנט שצוין.

9
00:00:22,200 --> 00:00:26,380
>> בפסאודו קוד, שהוא יותר
גרסה מזוקקת של המשפט הזה,

10
00:00:26,380 --> 00:00:29,840
אם המרכיב הראשון הוא מה ש
שאתה מחפש, אתה יכול להפסיק.

11
00:00:29,840 --> 00:00:33,930
אחרת, לעבור לפריט הבא ו
להמשיך שוב ושוב, עד שתמצא

12
00:00:33,930 --> 00:00:36,389
האלמנט, או שלא.

13
00:00:36,389 --> 00:00:38,680
אז אנחנו יכולים להשתמש ביניארי
אלגוריתם חיפוש, למשל,

14
00:00:38,680 --> 00:00:42,330
כדי למצוא את ערך היעד
תשעה במערך זה.

15
00:00:42,330 --> 00:00:43,870
ובכן אנחנו מתחילים בתחילת.

16
00:00:43,870 --> 00:00:45,970
אם זה מה שאנחנו
מחפש, אנחנו יכולים להפסיק.

17
00:00:45,970 --> 00:00:47,890
זה לא, אנחנו לא מחפשים 11.

18
00:00:47,890 --> 00:00:50,220
אז אחרת, לעבור לפריט הבא.

19
00:00:50,220 --> 00:00:51,510
>> אז אנחנו מסתכלים על 23.

20
00:00:51,510 --> 00:00:52,730
האם 23 מה אנחנו מחפשים?

21
00:00:52,730 --> 00:00:55,614
ובכן לא, אז אנחנו עוברים למקום הבא
אלמנט, והאלמנט הבא,

22
00:00:55,614 --> 00:00:57,780
ואנחנו ממשיכים עוברים
תהליך זה שוב ושוב

23
00:00:57,780 --> 00:01:01,030
ושוב, עד שננחת
במצב כזה.

24
00:01:01,030 --> 00:01:03,910
>> תשע הוא מה שאנחנו מחפשים,
והאלמנט הזה של המערך

25
00:01:03,910 --> 00:01:05,787
הוא, הערך שלו הוא תשע.

26
00:01:05,787 --> 00:01:08,120
וכך מצאנו את מה שאנחנו
מחפש, ואנחנו יכולים להפסיק.

27
00:01:08,120 --> 00:01:11,910
יש החיפוש ליניארי
הושלם, בהצלחה.

28
00:01:11,910 --> 00:01:15,370
>> אבל מה אם אנחנו מחפשים
אלמנט זה לא במערך שלנו.

29
00:01:15,370 --> 00:01:17,040
האם החיפוש ליניארי עדיין עובד?

30
00:01:17,040 --> 00:01:17,540
ובכן בטוח.

31
00:01:17,540 --> 00:01:19,947
אז אנחנו לחזור על תהליך זה
החל משעת האלמנט הראשון.

32
00:01:19,947 --> 00:01:21,780
אם זה מה שאנחנו
מחפש, אנחנו יכולים להפסיק.

33
00:01:21,780 --> 00:01:22,800
זה לא.

34
00:01:22,800 --> 00:01:25,020
אחרת, אנחנו עוברים לאלמנט הבא.

35
00:01:25,020 --> 00:01:29,050
>> אבל אנחנו יכולים לשמור חוזרים על תהליך זה,
בחינה כל אלמנט בתורו,

36
00:01:29,050 --> 00:01:31,720
בתקווה שנמצא את המספר 50.

37
00:01:31,720 --> 00:01:33,750
אבל אנחנו לא יודעים אם
אנחנו כבר מצאנו את המספר 50

38
00:01:33,750 --> 00:01:38,290
או אם אנחנו לא, עד שכבר יצאנו
מעל כל אלמנט של המערך.

39
00:01:38,290 --> 00:01:40,440
>> רק פעם אחת שעשינו
ושלבוא קצר,

40
00:01:40,440 --> 00:01:43,040
אנחנו יכולים להסיק ש
50 לא נמצא במערך.

41
00:01:43,040 --> 00:01:46,410
וכך החיפוש ליניארי
אלגוריתם, גם הוא נכשל, כשלעצמה.

42
00:01:46,410 --> 00:01:49,181
אבל לא במובן זה שהיא
לא הצליח לעשות את מה ש

43
00:01:49,181 --> 00:01:49,930
שאלנו אותו לעשות.

44
00:01:49,930 --> 00:01:52,390
>> זה היה לא מוצלח כב
כמה שזה לא מוצא 50,

45
00:01:52,390 --> 00:01:54,070
אבל 50 לא היו במערך.

46
00:01:54,070 --> 00:01:57,310
אבל יש לנו חיפשנו ממצה
דרך כל אלמנט

47
00:01:57,310 --> 00:02:00,550
וכך, בזמן שאנחנו לא מוצאים
שום דבר, חיפוש ליניארי עדיין

48
00:02:00,550 --> 00:02:05,230
גם אם תצליח
אלמנט הוא לא במערך.

49
00:02:05,230 --> 00:02:07,507
>> אז מה במקרה הגרוע ביותר
תרחיש עם חיפוש ליניארי?

50
00:02:07,507 --> 00:02:09,590
ובכן אנחנו צריכים להסתכל דרך
כל אלמנט,

51
00:02:09,590 --> 00:02:14,590
או בגלל שאלמנט היעד
הוא האלמנט האחרון של המערך,

52
00:02:14,590 --> 00:02:18,510
או האלמנט שאנחנו מחפשים לא
למעשה קיימים במערך בכל.

53
00:02:18,510 --> 00:02:19,760
מה התרחיש הטוב ביותר?

54
00:02:19,760 --> 00:02:22,430
ובכן, אנו עלולים למצוא את
אלמנט מייד.

55
00:02:22,430 --> 00:02:24,360
וכמה אלמנטים
אז אנחנו צריכים להסתכל

56
00:02:24,360 --> 00:02:26,859
במקרה הטוב,
אם אנחנו מסתכלים על זה

57
00:02:26,859 --> 00:02:28,400
ואנחנו מוצאים את זה בהתחלה?

58
00:02:28,400 --> 00:02:29,850
אנחנו יכולים להפסיק באופן מיידי.

59
00:02:29,850 --> 00:02:32,984
>> מה זה אומר על
מורכבות של חיפוש ליניארי?

60
00:02:32,984 --> 00:02:35,650
ובכן במקרה הגרוע ביותר, יש לנו
להסתכל על כל אלמנט.

61
00:02:35,650 --> 00:02:38,930
וכך זה פועל בO של
n, במקרה הגרוע ביותר.

62
00:02:38,930 --> 00:02:41,540
>> במקרה הטוב, אנחנו הולכים
למצוא את האלמנט מייד.

63
00:02:41,540 --> 00:02:44,750
וכך פועל באומגה של 1.

64
00:02:44,750 --> 00:02:45,780
>> אני דאג לויד.

65
00:02:45,780 --> 00:02:48,020
זה CS50.

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