1
00:00:00,000 --> 00:00:08,532
>> [เล่นดนตรี]

2
00:00:08,532 --> 00:00:12,060
>> ZAMYLA จัน: สิ่งแรกที่คุณอาจ
แจ้งให้ทราบเกี่ยวกับการค้นพบก็คือว่าเราอยู่แล้ว

3
00:00:12,060 --> 00:00:13,450
มีโค้ดที่เขียนสำหรับเรา

4
00:00:13,450 --> 00:00:15,160
นี้เรียกว่ารหัสการกระจาย

5
00:00:15,160 --> 00:00:18,000
ดังนั้นเราไม่ได้เพียงแค่เขียนของเราเอง
รหัสจากรอยขีดข่วนอีกต่อไป

6
00:00:18,000 --> 00:00:22,800
แต่เรากำลังการกรอกในช่องว่าง
ในบางรหัสที่มีอยู่แล้ว

7
00:00:22,800 --> 00:00:27,790
>> โปรแกรม find.c แจ้งให้สำหรับหมายเลข
เพื่อเติมกองหญ้า, การค้นหา

8
00:00:27,790 --> 00:00:32,189
กองหญ้าสำหรับเข็มที่ใช้ส่ง
และมันไม่นี้โดยการโทรและการจัดเรียง

9
00:00:32,189 --> 00:00:35,590
ฟังก์ชั่นการค้นหาที่กำหนดไว้
ใน helpers.c

10
00:00:35,590 --> 00:00:37,670
ดังนั้น find.c ถูกเขียนอยู่แล้ว

11
00:00:37,670 --> 00:00:40,770
งานของคุณคือการเขียนผู้ช่วยเหลือ

12
00:00:40,770 --> 00:00:41,870
>> ดังนั้นสิ่งที่เรากำลังทำอะไร

13
00:00:41,870 --> 00:00:44,210
เรากำลังดำเนินการทั้งสองฟังก์ชั่น

14
00:00:44,210 --> 00:00:49,030
ค้นหาซึ่งผลตอบแทนจริงถ้าค่า
ที่พบในกองหญ้ากลับ

15
00:00:49,030 --> 00:00:51,370
เท็จถ้าค่าเป็น
ไม่ได้อยู่ในกองหญ้า

16
00:00:51,370 --> 00:00:57,990
แล้วเรายังมีการดำเนินการจัดเรียง
ซึ่งเรียงลำดับแถวที่เรียกว่าค่า

17
00:00:57,990 --> 00:00:59,960
>> เพื่อให้ต่อสู้ของการค้นหา

18
00:00:59,960 --> 00:01:04,560
การค้นหาจะดำเนินการในปัจจุบันเป็น
ค้นหาเชิงเส้น แต่คุณสามารถทำอะไรได้มาก

19
00:01:04,560 --> 00:01:05,550
ดีกว่าว่า

20
00:01:05,550 --> 00:01:09,910
ค้นหาเชิงเส้นจะดำเนินการใน O
เวลา n ซึ่งคือค่อนข้างช้า

21
00:01:09,910 --> 00:01:13,850
แม้ว่าจะสามารถค้นหา
รายการใด ๆ ที่กำหนดให้

22
00:01:13,850 --> 00:01:20,130
งานของคุณคือการใช้การค้นหาแบบไบนารี
ซึ่งได้ใช้เวลา O ของบันทึก n

23
00:01:20,130 --> 00:01:21,130
นั่นคืออย่างรวดเร็ว

24
00:01:21,130 --> 00:01:23,170
>> แต่มีข้อตกลง

25
00:01:23,170 --> 00:01:27,600
ค้นหาแบบไบนารีสามารถค้นหา
ผ่านรายการที่เรียงลำดับก่อน

26
00:01:27,600 --> 00:01:30,370
ทำไมจึงเป็นเช่นนั้น

27
00:01:30,370 --> 00:01:32,620
>> ดีให้ดูตัวอย่าง

28
00:01:32,620 --> 00:01:36,280
ป.ร. ให้ไว้ ณ อาร์เรย์ของค่า, กองหญ้าที่
เรากำลังจะมองหา

29
00:01:36,280 --> 00:01:37,130
เข็ม

30
00:01:37,130 --> 00:01:40,460
และในตัวอย่างนี้
สามจำนวนเต็ม

31
00:01:40,460 --> 00:01:44,130
วิธีการที่ค้นหาแบบไบนารีทำงานคือ
เราเปรียบเทียบค่ากลางของ

32
00:01:44,130 --> 00:01:48,370
อาร์เรย์ที่เข็มเหมือนวิธี
เราเปิดสมุดโทรศัพท์กลาง

33
00:01:48,370 --> 00:01:50,660
ในสัปดาห์หน้าศูนย์

34
00:01:50,660 --> 00:01:54,650
>> ดังนั้นหลังจากการเปรียบเทียบค่ากลาง
เข็มคุณสามารถทิ้งอย่างใดอย่างหนึ่ง

35
00:01:54,650 --> 00:01:58,530
ด้านซ้ายหรือด้านขวาของอาร์เรย์
โดยกระชับขอบเขตของคุณ

36
00:01:58,530 --> 00:02:03,390
ในกรณีนี้ตั้งแต่สามเข็มของเรา
น้อยกว่า 10 ค่ากลาง

37
00:02:03,390 --> 00:02:05,990
ผูกพันที่เหมาะสมสามารถลด

38
00:02:05,990 --> 00:02:08,400
แต่พยายามที่จะทำให้ขอบเขตของคุณ
แน่นที่สุดเท่าที่ทำได้

39
00:02:08,400 --> 00:02:11,630
ถ้าค่าตรงกลางไม่ได้เป็นเข็ม
แล้วคุณจะรู้ว่าคุณไม่จำเป็นต้อง

40
00:02:11,630 --> 00:02:13,010
รวมไว้ในการค้นหาของคุณ

41
00:02:13,010 --> 00:02:17,310
ดังนั้นคุณผูกพันที่เหมาะสมสามารถกระชับ
ขอบเขตการค้นหาเพียงเล็กน้อยมากขึ้น

42
00:02:17,310 --> 00:02:21,770
และอื่น ๆ และอื่น ๆ จน
คุณพบว่าเข็มของคุณ

43
00:02:21,770 --> 00:02:23,480
>> ดังนั้นสิ่งที่จะ pseudocode มีลักษณะอย่างไร

44
00:02:23,480 --> 00:02:28,420
ดีในขณะที่เรายังคงมองผ่าน
รายการและยังมีองค์ประกอบ

45
00:02:28,420 --> 00:02:33,690
ดูในเราจะกลางรายการ
และเปรียบเทียบค่ากลางที่

46
00:02:33,690 --> 00:02:34,950
เข็มของเรา

47
00:02:34,950 --> 00:02:37,310
หากพวกเขากำลังเท่ากันแล้วนั่นหมายความว่าเราได้
พบเข็มและที่เราสามารถทำได้

48
00:02:37,310 --> 00:02:38,990
กลับจริง

49
00:02:38,990 --> 00:02:42,870
>> มิฉะนั้นถ้าเข็มน้อยกว่า
ค่ากลางแล้วนั่นหมายความว่าเรา

50
00:02:42,870 --> 00:02:47,280
สามารถทิ้งครึ่งหนึ่งที่เหมาะสมและเพียงแค่
ค้นหาที่ด้านซ้ายของแถว

51
00:02:47,280 --> 00:02:51,090
มิฉะนั้นเราจะค้นหา
ด้านขวาของอาร์เรย์

52
00:02:51,090 --> 00:02:54,410
และในท้ายที่สุดถ้าคุณไม่ได้มี
องค์ประกอบอื่น ๆ ที่เหลือในการค้นหา แต่คุณ

53
00:02:54,410 --> 00:02:58,050
ยังไม่พบเ​​ข็มของคุณยังแล้วคุณ
กลับเท็จเพราะเข็ม

54
00:02:58,050 --> 00:03:01,890
แน่นอนไม่ได้อยู่ในกองหญ้า

55
00:03:01,890 --> 00:03:05,270
>> ตอนนี้สิ่งที่ระเบียบเกี่ยวกับ pseudocode นี้
ในการค้นหาไบนารีที่จะสามารถ

56
00:03:05,270 --> 00:03:09,940
ตีความว่าเป็นอย่างใดอย่างหนึ่งซ้ำแล้วซ้ำอีก
หรือการดำเนินการซ้ำ

57
00:03:09,940 --> 00:03:13,810
ดังนั้นมันจะซ้ำถ้าคุณเรียกว่า
ฟังก์ชันการค้นหาในการค้นหา

58
00:03:13,810 --> 00:03:17,350
ฟังก์ชั่นในครึ่งหนึ่งของอาร์เรย์ทั้ง

59
00:03:17,350 --> 00:03:21,030
เราจะครอบคลุมการเรียกซ้ำอีกเล็กน้อยในภายหลัง
แน่นอน แต่ไม่ทราบว่ามันเป็น

60
00:03:21,030 --> 00:03:24,190
ตัวเลือกถ้าคุณต้องการที่จะลอง

61
00:03:24,190 --> 00:03:26,030
>> ตอนนี้ให้ดูที่การจัดเรียง

62
00:03:26,030 --> 00:03:30,750
เรียงใช้อาร์เรย์และจำนวนเต็ม
n ซึ่งเป็นขนาดของอาร์เรย์

63
00:03:30,750 --> 00:03:34,030
ขณะนี้มีชนิดที่แตกต่างกัน
แปลกและคุณสามารถดูที่บาง

64
00:03:34,030 --> 00:03:36,370
กางเกงขาสั้นเพื่อการสาธิตและคำอธิบาย

65
00:03:36,370 --> 00:03:39,580
ประเภทผลตอบแทนของเรา
ฟังก์ชั่นการจัดเรียงจะถือเป็นโมฆะ

66
00:03:39,580 --> 00:03:43,580
เพื่อที่ว่าหมายความว่าเราจะไม่
เพื่อกลับอาร์เรย์ใด ๆ จากการจัดเรียง

67
00:03:43,580 --> 00:03:48,140
เราจริงจะมีการเปลี่ยนแปลงมาก
อาร์เรย์ที่ผ่านเข้ามาในเรา

68
00:03:48,140 --> 00:03:52,290
>> และที่เป็นไปได้เพราะเป็นอาร์เรย์
ผ่านการอ้างอิงในซีตอนนี้เราจะ

69
00:03:52,290 --> 00:03:55,290
ดูรายละเอียดเพิ่มเติมเกี่ยวกับเรื่องนี้ในภายหลัง แต่
ความแตกต่างที่สำคัญระหว่างการผ่าน

70
00:03:55,290 --> 00:03:59,340
ในสิ่งที่ต้องการจำนวนเต็มและผ่าน
ในอาร์เรย์คือว่าเมื่อคุณ

71
00:03:59,340 --> 00:04:03,490
ผ่านในจำนวนเต็ม C เป็นเพียงการไป
ทำสำเนาของจำนวนเต็มที่และผ่าน

72
00:04:03,490 --> 00:04:04,450
มันฟังก์ชั่น

73
00:04:04,450 --> 00:04:08,530
ตัวแปรเดิมจะไม่สามารถเปลี่ยนแปลงได้
เมื่อทำงานเสร็จสิ้น

74
00:04:08,530 --> 00:04:12,480
กับอาร์เรย์ในมืออื่น ๆ ก็
จะไม่ทำสำเนาและคุณจะ

75
00:04:12,480 --> 00:04:17,910
จริงจะแก้ไข
อาร์เรย์ตัวเองมาก

76
00:04:17,910 --> 00:04:21,269
>> ดังนั้นประเภทหนึ่งของการจัดเรียงเป็น
เรียงลำดับการเลือก

77
00:04:21,269 --> 00:04:24,750
เรียงลำดับการเลือกทำงานโดยเริ่มต้นที่
จุดเริ่มต้นและจากนั้นคุณย้ำ

78
00:04:24,750 --> 00:04:26,820
กว่าและหาองค์ประกอบที่เล็กที่สุด

79
00:04:26,820 --> 00:04:30,710
แล้วคุณสลับที่เล็กที่สุด
องค์ประกอบกับคนแรก

80
00:04:30,710 --> 00:04:34,360
แล้วคุณจะย้ายไปยังองค์ประกอบที่สอง
หาที่เล็กที่สุดต่อไป

81
00:04:34,360 --> 00:04:38,320
องค์ประกอบและจากนั้นสลับที่กับ
องค์ประกอบที่สองในอาร์เรย์เพราะ

82
00:04:38,320 --> 00:04:41,100
องค์ประกอบแรกจะเรียงลำดับแล้ว

83
00:04:41,100 --> 00:04:45,370
และอื่น ๆ แล้วคุณยังคงสำหรับทุก
องค์ประกอบในการระบุที่เล็กที่สุด

84
00:04:45,370 --> 00:04:47,690
ค่าและการแลกเปลี่ยนมันออกมา

85
00:04:47,690 --> 00:04:53,460
>> เพราะเราเท่ากับ 0, องค์ประกอบแรกมาก
n การลบ 1, คุณจะเปรียบเทียบ

86
00:04:53,460 --> 00:04:57,820
ทุกค่าถัดไปหลังจากนั้นและหา
ดัชนีของค่าต่ำสุด

87
00:04:57,820 --> 00:05:02,520
เมื่อคุณพบดัชนีค่าต่ำสุด
คุณสามารถสลับค่าของแถวที่

88
00:05:02,520 --> 00:05:05,930
ขั้นต่ำและแถวที่หนึ่ง

89
00:05:05,930 --> 00:05:09,760
>> ประเภทของการจัดเรียงอื่นที่คุณสามารถ
ดำเนินการจัดเรียงฟอง

90
00:05:09,760 --> 00:05:14,380
ดังนั้นการจัดเรียงฟอง iterates ผ่านรายการ
เปรียบเทียบองค์ประกอบอยู่ติดกันและ

91
00:05:14,380 --> 00:05:17,720
การแลกเปลี่ยนองค์ประกอบที่
อยู่ในลำดับที่ไม่ถูกต้อง

92
00:05:17,720 --> 00:05:22,380
และวิธีนี้เป็นองค์ประกอบที่ใหญ่ที่สุด
ฟองจะสิ้นสุด

93
00:05:22,380 --> 00:05:28,070
และรายการที่มีการจัดเรียงอีกไม่มาก
องค์ประกอบได้รับการสลับ

94
00:05:28,070 --> 00:05:31,920
>> ดังนั้นผู้เป็นสองตัวอย่างของการจัดเรียง
ขั้นตอนวิธีการที่คุณสามารถใช้เพื่อ

95
00:05:31,920 --> 00:05:33,230
โปรแกรมพบ

96
00:05:33,230 --> 00:05:37,350
เมื่อคุณเสร็จสิ้นการจัดเรียงและคุณได้
ทำค้นหาคุณดำเนินการเสร็จสิ้น

97
00:05:37,350 --> 00:05:39,720
ชื่อของฉันคือ Zamyla และนี่คือ CS50

98
00:05:39,720 --> 00:05:46,987
>> [เล่นดนตรี]