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