1
00:00:00,000 --> 00:00:13,300

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Привіт, я Роб.

3
00:00:15,010 --> 00:00:16,790
Як ми використовуємо бінарний пошук?

4
00:00:16,790 --> 00:00:18,770
Давайте з'ясуємо.

5
00:00:18,770 --> 00:00:23,400
Так, зверніть увагу, що цей пошук ми збираємося
реалізувати рекурсивно.

6
00:00:23,400 --> 00:00:27,470
Крім того, можна реалізувати бінарний пошук
багаторазово, так що якщо ви це зробили,

7
00:00:27,470 --> 00:00:29,280
це абсолютно нормально.

8
00:00:29,280 --> 00:00:32,820
>> Тепер спочатку, давайте пам'ятати, що
Параметри для пошуку призначені для.

9
00:00:32,820 --> 00:00:36,120
Тут ми бачимо десяткового значення, яке
має бути значення користувач

10
00:00:36,120 --> 00:00:37,320
пошук.

11
00:00:37,320 --> 00:00:40,800
Ми бачимо масив Int цінності, які
це масив, в якому ми

12
00:00:40,800 --> 00:00:42,520
пошук значення.

13
00:00:42,520 --> 00:00:45,602
І ми бачимо, Int N, який є
довжина нашого масиву.

14
00:00:45,602 --> 00:00:47,410
>> Тепер, перше, що в першу чергу.

15
00:00:47,410 --> 00:00:51,350
Ми перевіряємо, якщо п дорівнює 0, в
цьому випадку ми повернутися помилковим.

16
00:00:51,350 --> 00:00:54,770
Ось тільки говорити, якщо у нас є порожній
Масив, вартість явно не буде в

17
00:00:54,770 --> 00:00:57,860
порожній масив, тому ми можемо повернутися помилковим.

18
00:00:57,860 --> 00:01:01,250
>> Тепер, ми насправді хочемо зробити двійковий
Пошук частина бінарного пошуку.

19
00:01:01,250 --> 00:01:04,780
Так, ми хочемо знайти середину
елемент цього масиву.

20
00:01:04,780 --> 00:01:09,130
Тут ми говоримо середнього дорівнює п ділиться
на 2, з середини елемент

21
00:01:09,130 --> 00:01:12,240
буде довжина
розділити на 2 наш масив.

22
00:01:12,240 --> 00:01:15,040
Тепер ми збираємося, щоб перевірити, якщо
середній елемент дорівнює значенню, коли ми знаходимося

23
00:01:15,040 --> 00:01:16,160
пошук.

24
00:01:16,160 --> 00:01:21,030
Так що, якщо значення середнього дорівнює вартості, ми
може повернутися вірно, оскільки ми виявили, що

25
00:01:21,030 --> 00:01:22,810
значення в масиві.

26
00:01:22,810 --> 00:01:26,380
>> Але якщо це не так, тепер
ми повинні зробити рекурсивний

27
00:01:26,380 --> 00:01:27,840
крок бінарного пошуку.

28
00:01:27,840 --> 00:01:30,450
Нам потрібно шукати або
зліва від масиву або

29
00:01:30,450 --> 00:01:32,320
середній масиву.

30
00:01:32,320 --> 00:01:39,280
Так от, ми говоримо, якщо значення в середині є
менше, ніж значення, що означає, що вартість

31
00:01:39,280 --> 00:01:41,350
було більше, ніж у середині
масиву.

32
00:01:41,350 --> 00:01:45,790
Так значення має бути праворуч від
елемент, який ми тільки що дивилися.

33
00:01:45,790 --> 00:01:48,090
>> Так от, ми збираємося
пошук рекурсивно.

34
00:01:48,090 --> 00:01:50,320
І ми будемо дивитися на те, що ми передаємо
до цього в секунду.

35
00:01:50,320 --> 00:01:53,440
Але ми збираємося шукати в
Право середнього елемента.

36
00:01:53,440 --> 00:01:57,710
А в іншому випадку, це означає, що
значення було менше, ніж у середині

37
00:01:57,710 --> 00:02:00,660
Масив, і таким чином ми збираємося
шукати вліво.

38
00:02:00,660 --> 00:02:03,520
Тепер ліва буде
трохи легше дивитися.

39
00:02:03,520 --> 00:02:07,770
Таким чином, ми бачимо, що ми рекурсивно
виклику пошуку, де перший

40
00:02:07,770 --> 00:02:10,120
аргумент, знову ж, значення
ми шукаємо більш.

41
00:02:10,120 --> 00:02:14,970
Другий аргумент буде
Масив, ми шукали більше.

42
00:02:14,970 --> 00:02:17,090
І останній елемент тепер є середній.

43
00:02:17,090 --> 00:02:21,650
Пам'ятайте останній параметр є нашим внутр
п, так що це довжина нашого масиву.

44
00:02:21,650 --> 00:02:25,310
>> У рекурсивному виклику для пошуку, ми
тепер кажуть, що довжина

45
00:02:25,310 --> 00:02:27,230
масив середній.

46
00:02:27,230 --> 00:02:32,900
Так що, якщо наш масив був розміром 20 і ми
Пошук за індексом 10, так як середина

47
00:02:32,900 --> 00:02:36,930
20 розділити на 2, що означає, що ми
проходячи 10 як новий

48
00:02:36,930 --> 00:02:38,300
довжина нашого масиву.

49
00:02:38,300 --> 00:02:41,910
Пам'ятайте, що коли у вас є масив
довжиною 10, це означає, що діє

50
00:02:41,910 --> 00:02:45,450
елементи знаходяться в індексів від 0 до 9.

51
00:02:45,450 --> 00:02:50,120
Так що це саме те, що ми хочемо
вказати наш оновлений масив - лівий

52
00:02:50,120 --> 00:02:53,010
Масив з середнього елемента.

53
00:02:53,010 --> 00:02:55,710
>> Так, у пошуках до права
трохи складніше.

54
00:02:55,710 --> 00:03:00,170
Тепер спочатку давайте розглянемо довжину
масиву на право

55
00:03:00,170 --> 00:03:01,240
середній елемент.

56
00:03:01,240 --> 00:03:08,390
Так що, якщо наш масив був розміром п, то
Новий масив буде мати розмір н мінус

57
00:03:08,390 --> 00:03:10,140
середній мінус 1.

58
00:03:10,140 --> 00:03:12,530
Отже, давайте думати про н мінус середині.

59
00:03:12,530 --> 00:03:18,710
>> Знову ж, якщо масив були розміром 20 і
ми ділимо на 2, щоб отримати середину,

60
00:03:18,710 --> 00:03:23,540
так середина 10, то п мінус середнього
збирається дати нам 10, так 10

61
00:03:23,540 --> 00:03:25,330
елементи праворуч від середини.

62
00:03:25,330 --> 00:03:27,780
Але у нас є цей мінус
1, так як ми не хочемо, щоб

63
00:03:27,780 --> 00:03:29,700
включають саму середину.

64
00:03:29,700 --> 00:03:34,190
Так н мінус середній мінус 1 дає нам
Загальна кількість елементів праворуч

65
00:03:34,190 --> 00:03:36,800
середнього індексу в масиві.

66
00:03:36,800 --> 00:03:41,870
>> Тепер ось, пам'ятайте, що середній
параметром є масив значень.

67
00:03:41,870 --> 00:03:46,180
Так от, ми передаємо
оновлення значення масиву.

68
00:03:46,180 --> 00:03:50,930
Ці значення плюс середній плюс 1 є
фактично кажучи рекурсивний виклик

69
00:03:50,930 --> 00:03:56,460
Пошук, переходячи в новий масив, де
що новий масив починається в середині

70
00:03:56,460 --> 00:03:59,370
плюс один з наших первинних значень масиву.

71
00:03:59,370 --> 00:04:05,400
>> Альтернативний синтаксис, що тепер,
ви почали бачити покажчики, є

72
00:04:05,400 --> 00:04:10,170
значення амперсенд середнього плюс 1.

73
00:04:10,170 --> 00:04:17,149
Таким чином, захопити адресу середині
плюс один елемент цінностей.

74
00:04:17,149 --> 00:04:23,690
>> Тепер, якщо ви не були зручні
зміни масив, можливо, вам

75
00:04:23,690 --> 00:04:28,900
може також реалізували це, використовуючи
рекурсивний допоміжна функція, де

76
00:04:28,900 --> 00:04:31,680
що допоміжна функція приймає
більше аргументів.

77
00:04:31,680 --> 00:04:36,610
Так замість того, щоб тільки значення,
масив, і розмір масиву,

78
00:04:36,610 --> 00:04:42,315
допоміжна функція може зайняти більше
аргументи, в тому числі понад низьким індексом

79
00:04:42,315 --> 00:04:45,280
що ви дбаєте про в масиві
і верхній індекс, що ви дбаєте

80
00:04:45,280 --> 00:04:46,300
про масиві.

81
00:04:46,300 --> 00:04:49,770
>> І так відстеження і нижня
індекс і верхній індекс, ви не

82
00:04:49,770 --> 00:04:52,780
потрібно постійно змінювати
вихідні значення масиву.

83
00:04:52,780 --> 00:04:56,390
Ви можете просто продовжувати
використовувати масив значень.

84
00:04:56,390 --> 00:04:59,540
Але ось, зверніть увагу, ми не потребуємо помічника
функціонувати до тих пір, як ми

85
00:04:59,540 --> 00:05:01,760
готові змінити оригінал
значення масиву.

86
00:05:01,760 --> 00:05:05,020
Ми готові передати до
Оновлений значення.

87
00:05:05,020 --> 00:05:09,140
>> Тепер, ми не можемо бінарний пошук по
масив, який є несортоване.

88
00:05:09,140 --> 00:05:12,220
Отже, давайте отримати цю розібратися.

89
00:05:12,220 --> 00:05:17,650
Тепер, зверніть увагу, що сортування останні два
параметри десяткового значення, яке є

90
00:05:17,650 --> 00:05:21,110
Масив, ми сортування і Int N,
що довжина масиву,

91
00:05:21,110 --> 00:05:22,250
ми сортування.

92
00:05:22,250 --> 00:05:24,840
Отже, ось ми хочемо реалізувати
алгоритм сортування

93
00:05:24,840 --> 00:05:26,690
що є о н в квадраті.

94
00:05:26,690 --> 00:05:30,560
Ви можете вибрати міхур сортування, відбору
сортувати, або сортування вставками, або

95
00:05:30,560 --> 00:05:32,670
деякий інший вид у нас не
бачив у класі.

96
00:05:32,670 --> 00:05:36,380
Але тут, ми збираємося
використовувати вибору роду.

97
00:05:36,380 --> 00:05:40,030
>> Так, ми збираємося ітерації
протягом всього масиву.

98
00:05:40,030 --> 00:05:44,360
Ну, ось ми бачимо, що ми ітерації
від 0 до п мінус 1.

99
00:05:44,360 --> 00:05:45,990
Чому б не все, аж до п?

100
00:05:45,990 --> 00:05:49,320
Ну, якщо ми вже відсортовані першим
п мінус 1 елементів, то

101
00:05:49,320 --> 00:05:54,420
найостанніший елемент, що вже має бути
в правильному місці, так сортування по

102
00:05:54,420 --> 00:05:56,520
весь масив.

103
00:05:56,520 --> 00:05:58,770
>> Тепер згадайте, як вибір
начебто працює.

104
00:05:58,770 --> 00:06:01,950
Ми збираємося йти протягом всього масиву
шукаю мінімального значення в

105
00:06:01,950 --> 00:06:04,480
масив і пряника, що
на самому початку.

106
00:06:04,480 --> 00:06:07,610
Тоді ми збираємося йти протягом всього
Масив знову шукає другого

107
00:06:07,610 --> 00:06:10,410
найменший елемент, і палиця, що
на другій позиції в

108
00:06:10,410 --> 00:06:12,100
масив, і так далі.

109
00:06:12,100 --> 00:06:14,330
Отже, ось що це робить.

110
00:06:14,330 --> 00:06:17,290
>> Тут ми бачимо, що ми
установки поточного мінімуму

111
00:06:17,290 --> 00:06:20,030
значення для г-го індексу.

112
00:06:20,030 --> 00:06:23,160
Так на першій ітерації, ми збираємося
розглянути мінімальне значення бути

113
00:06:23,160 --> 00:06:25,030
початок нашого масиву.

114
00:06:25,030 --> 00:06:28,500
Тоді, ми збираємося для перебору
Інша частина масиву, перевірка на

115
00:06:28,500 --> 00:06:31,870
побачити, якщо є які-небудь елементи менше, ніж
той, який ми нині

116
00:06:31,870 --> 00:06:33,900
враховуючи мінімум.

117
00:06:33,900 --> 00:06:38,840
>> Так от, значення J плюс один - це
менше, ніж те, що ми в даний час

118
00:06:38,840 --> 00:06:40,380
враховуючи мінімум.

119
00:06:40,380 --> 00:06:42,940
Тоді ми збираємося оновити те, що
ми думаємо, що це мінімальний, щоб

120
00:06:42,940 --> 00:06:44,640
індекс J плюс 1.

121
00:06:44,640 --> 00:06:48,540
Так, зробити це через весь масив,
і після цього протягом циклу, мінімум

122
00:06:48,540 --> 00:06:53,160
має бути мінімальним елементом з
я-у позицію в масиві.

123
00:06:53,160 --> 00:06:57,350
>> Як тільки у нас є, що ми можемо поміняти
Мінімальне значення в м-й позиції

124
00:06:57,350 --> 00:06:58,230
в масиві.

125
00:06:58,230 --> 00:07:00,130
Так що це всього лише стандартний підкачки.

126
00:07:00,130 --> 00:07:03,940
Ми зберігаємо в тимчасовому значенні -
значення я-я в масиві -

127
00:07:03,940 --> 00:07:08,460
значення поміщається г-й в масиві
Мінімальне значення, яке належить там,

128
00:07:08,460 --> 00:07:13,580
а потім зберегти назад в де
струму мінімальне значення раніше

129
00:07:13,580 --> 00:07:16,460
I-й значення в масиві, так
що ми не втратили його.

130
00:07:16,460 --> 00:07:20,510
>> Так, що триває
наступна ітерація.

131
00:07:20,510 --> 00:07:23,480
Ми почнемо шукати другу
Мінімальне значення і вставте, що в

132
00:07:23,480 --> 00:07:24,590
Друга позиція.

133
00:07:24,590 --> 00:07:27,440
На третій ітерації, ми будемо шукати
третє значення мінімальної та вставка

134
00:07:27,440 --> 00:07:31,550
що в третьому положенні, і тому
, Поки у нас немає відсортований масив.

135
00:07:31,550 --> 00:07:33,820
Мене звуть Боб, і це
був вибір роду.

136
00:07:33,820 --> 00:07:39,456