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
在这里，我们看到的int值，这是
认为是用户的价值

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
我们看到整数n，它是
我们的阵列的长度。

14
00:00:45,602 --> 00:00:47,410
>> 现在，第一件事情第一。

15
00:00:47,410 --> 00:00:51,350
我们检查是否n等于0，在
这种情况下，我们返回false。

16
00:00:51,350 --> 00:00:54,770
这只是说，如果我们有一个空
数组，值显然不是在

17
00:00:54,770 --> 00:00:57,860
空数组，所以我们可以返回false。

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
在这里，我们说中间等于n除
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
记住最后一个参数是我们的诠释
N，所以这是我们的数组的长度。

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
所以，如果我们的数组是大小为n，则
新的数组将是大小为n减去

57
00:03:08,390 --> 00:03:10,140
中间减1。

58
00:03:10,140 --> 00:03:12,530
所以，让我们想到的n个减去中间。

59
00:03:12,530 --> 00:03:18,710
>> 再次，如果该数组的大小分别为20和
我们除以2得到的中间，

60
00:03:18,710 --> 00:03:23,540
所以中间是10，则n减去中间
是想给我们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
因此n减去中间减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
因此，抓住中间的地址
值加1的元素。

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
现在，请注意排序是近两年
参数int值，这是

90
00:05:17,650 --> 00:05:21,110
数组，我们正在整理，诠释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
这是二六，O n的平方。

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到n减去1。

99
00:05:44,360 --> 00:05:45,990
为什么不一路攀升到n？

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
值到第i个指数。

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
>> 所以在这里，值Ĵ加上一个 - 那就是
低于我们目前

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
所以，做整个数组，
而在此之后的for循环，最小

122
00:06:48,540 --> 00:06:53,160
应的最小元素从
阵列中的第i个位置。

123
00:06:53,160 --> 00:06:57,350
>> 一旦我们有了这个，我们可以交换
最小值到的第i个位置

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
我们存储在一个临时的价值 - 
阵列中的第i个值 - 

127
00:07:03,940 --> 00:07:08,460
放入数组中的第i个值的
属于有最小值，

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