1
00:00:00,000 --> 00:00:09,560

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

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

4
00:00:14,520 --> 00:00:16,219
นี้เรียกว่ารหัสการกระจาย

5
00:00:16,219 --> 00:00:19,060
ดังนั้นเราไม่ได้เพียงแค่เขียนของเราเอง
รหัสจากรอยขีดข่วนอีกต่อไป

6
00:00:19,060 --> 00:00:23,870
แต่เรากำลังการกรอกในช่องว่าง
ในบางรหัสที่มีอยู่แล้ว

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

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

9
00:00:33,260 --> 00:00:36,660
ฟังก์ชั่นการค้นหาที่กำหนดไว้
ใน helpers.c

10
00:00:36,660 --> 00:00:38,740
ดังนั้น find.c ถูกเขียนอยู่แล้ว

11
00:00:38,740 --> 00:00:41,840
งานของคุณคือการเขียนผู้ช่วยเหลือ

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

13
00:00:42,940 --> 00:00:45,270
เรากำลังดำเนินการทั้งสองฟังก์ชั่น

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

15
00:00:50,110 --> 00:00:52,430
เท็จถ้าค่าเป็น
ไม่ได้อยู่ในกองหญ้า

16
00:00:52,430 --> 00:00:59,060
แล้วเรายังมีการดำเนินการเรียงลำดับ
ซึ่งเรียงลำดับแถวที่เรียกว่าค่า

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

18
00:01:01,120 --> 00:01:04,550
>> การค้นหาจะดำเนินการในปัจจุบัน
เช่นค้นหาเชิงเส้น

19
00:01:04,550 --> 00:01:06,620
แต่คุณสามารถทำดีกว่าที่

20
00:01:06,620 --> 00:01:11,610
ค้นหาเชิงเส้นจะดำเนินการใน O ของ n
เวลาที่ช้ามากแม้ว่ามันจะ

21
00:01:11,610 --> 00:01:14,920
สามารถค้นหารายการใด ๆ ที่กำหนดให้

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

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

24
00:01:22,200 --> 00:01:24,240
>> แต่มีข้อตกลง

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

26
00:01:28,910 --> 00:01:31,450
ทำไมจึงเป็นเช่นนั้น

27
00:01:31,450 --> 00:01:33,690
ดีขอดูตัวอย่าง

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

29
00:01:37,350 --> 00:01:41,510
เข็มและในนี้
เช่นเลขที่ 3

30
00:01:41,510 --> 00:01:45,220
>> วิธีการที่ค้นหาแบบไบนารีทำงานคือ
เราเปรียบเทียบค่ากลางของ

31
00:01:45,220 --> 00:01:49,430
อาร์เรย์ที่เข็มเหมือนวิธี
เราเปิดสมุดโทรศัพท์กลาง

32
00:01:49,430 --> 00:01:51,720
หน้าในสัปดาห์ที่ 0

33
00:01:51,720 --> 00:01:55,710
ดังนั้นหลังจากการเปรียบเทียบค่ากลาง
เข็มคุณสามารถทิ้งอย่างใดอย่างหนึ่ง

34
00:01:55,710 --> 00:01:59,620
ด้านซ้ายหรือด้านขวาของอาร์เรย์
โดยกระชับขอบเขตของคุณ

35
00:01:59,620 --> 00:02:04,450
ในกรณีนี้ตั้งแต่ 3 เข็มของเราเป็น
น้อยกว่า 10 ค่ากลาง

36
00:02:04,450 --> 00:02:07,060
ผูกพันที่เหมาะสมสามารถลด

37
00:02:07,060 --> 00:02:09,470
>> แต่พยายามที่จะทำให้ขอบเขตของคุณ
แน่นที่สุดเท่าที่ทำได้

38
00:02:09,470 --> 00:02:12,690
ถ้าค่าตรงกลางไม่ได้เป็นเข็ม
แล้วคุณจะรู้ว่าคุณไม่จำเป็นต้อง

39
00:02:12,690 --> 00:02:14,070
รวมไว้ในการค้นหาของคุณ

40
00:02:14,070 --> 00:02:18,390
ดังนั้นตอนของคุณผูกพันสามารถกระชับ
ขอบเขตการค้นหาเพียงเล็กน้อยมากขึ้น

41
00:02:18,390 --> 00:02:22,840
และอื่น ๆ และอื่น ๆ จน
คุณพบว่าเข็มของคุณ

42
00:02:22,840 --> 00:02:24,580
>> ดังนั้นสิ่งที่จะหลอก
รหัสมีลักษณะอย่างไร

43
00:02:24,580 --> 00:02:28,980
ดีในขณะที่เรายังคงมองผ่าน
รายการและยังคงมี

44
00:02:28,980 --> 00:02:33,540
องค์ประกอบที่จะมองไปในเราจะอยู่ตรงกลาง
ของรายการและเปรียบเทียบว่า

45
00:02:33,540 --> 00:02:36,020
ค่ากลางเข็มของเรา

46
00:02:36,020 --> 00:02:38,380
หากพวกเขากำลังเท่ากันแล้วนั่นหมายความว่าเราได้
พบเข็มและที่เราสามารถทำได้

47
00:02:38,380 --> 00:02:40,160
กลับจริง

48
00:02:40,160 --> 00:02:43,940
>> มิฉะนั้นถ้าเข็มน้อยกว่า
ค่ากลางแล้วนั่นหมายความว่าเรา

49
00:02:43,940 --> 00:02:48,350
สามารถทิ้งครึ่งหนึ่งที่เหมาะสมและเพียงแค่
ค้นหาที่ด้านซ้ายของแถว

50
00:02:48,350 --> 00:02:51,860
มิฉะนั้นเราจะค้นหา
ด้านขวาของอาร์เรย์

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

52
00:02:55,470 --> 00:02:58,030
ยังไม่พบเ​​ข็มของคุณยัง
แล้วคุณกลับเท็จ

53
00:02:58,030 --> 00:03:02,960
เพราะเข็มที่แน่นอน
ไม่ได้อยู่ในกองหญ้า

54
00:03:02,960 --> 00:03:06,200
>> ตอนนี้สิ่งหนึ่งที่ระเบียบเกี่ยวกับการหลอกนี้
ในการค้นหารหัสเลขฐานสองก็คือว่ามันสามารถ

55
00:03:06,200 --> 00:03:11,000
ถูกตีความว่าเป็นอย่างใดอย่างหนึ่งซ้ำแล้วซ้ำอีก
หรือการดำเนินการซ้ำ

56
00:03:11,000 --> 00:03:14,900
ดังนั้นมันจะซ้ำถ้าคุณเรียกว่า
ฟังก์ชันการค้นหาในการค้นหา

57
00:03:14,900 --> 00:03:18,400
ฟังก์ชั่นในครึ่งหนึ่งของอาร์เรย์ทั้ง

58
00:03:18,400 --> 00:03:20,750
เราจะครอบคลุมการเรียกซ้ำบิต
ต่อมาในหลักสูตร

59
00:03:20,750 --> 00:03:23,210
แต่รู้ว่ามันเป็นตัวเลือกที่
ถ้าคุณต้องการที่จะลอง

60
00:03:23,210 --> 00:03:24,460