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
DOUG LLOYD เป็น Linear
ค้นหาเป็นอัลกอริทึมที่เรา

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
>> ใน pseudocode ซึ่งเป็นมากขึ้น
กลั่นรุ่นของประโยคนี้

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
และเพื่อให้มันทำงานในโอ
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