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
часу н, який є досить повільним.

21
00:01:09,910 --> 00:01:13,850
Хоча, він може шукати
будь-який список дано йому.

22
00:01:13,850 --> 00:01:20,130
Ваше завдання полягає в реалізації бінарний пошук,
який під час виконання O з журналу п.

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
>> Отже, що ж псевдокод виглядати?

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
>> Тепер акуратно річ про це псевдокоде
в двійкового пошуку є те, що він може бути

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
Сортувати приймає масив і ціле
п, що розмір масиву.

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, найперший елемент
п мінус 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
Так бульбашкового сортування перебирає список
порівнянні сусідніх елементів і

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
>> [Музика грає]