1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [二进制搜索]

2
00:00:02,000 --> 00:00:04,000
[帕特里克·施密德 - 哈佛大学]

3
00:00:04,000 --> 00:00:07,000
[这是CS50。 -  CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> 如果我给你的迪士尼人物名称按字母顺序排列的列表

5
00:00:09,000 --> 00:00:11,000
问你找到米老鼠，

6
00:00:11,000 --> 00:00:13,000
你会如何​​去这样做呢？

7
00:00:13,000 --> 00:00:15,000
一个显而易见的方法将是从开始扫描列表

8
00:00:15,000 --> 00:00:18,000
并检查每一个名字，看它是否是米奇。

9
00:00:18,000 --> 00:00:22,000
但是，当你阅读阿拉丁，爱丽丝，碧浪，等等，

10
00:00:22,000 --> 00:00:25,000
你很快就会意识到，在前面的列表是不是一个好主意。

11
00:00:25,000 --> 00:00:29,000
好吧，也许你应该开始从列表末尾向后工作。

12
00:00:29,000 --> 00:00:33,000
现在你看泰山，史迪仔，白雪公主，等等。

13
00:00:33,000 --> 00:00:36,000
不过，这似乎并不像最好的方式去了解它。

14
00:00:36,000 --> 00:00:38,000
>> 那么，另一种方式，你可以去这样做的，是尽量缩小

15
00:00:38,000 --> 00:00:41,000
名称的列表，你必须看。

16
00:00:41,000 --> 00:00:43,000
既然你知道，他们是按字母顺序排列，

17
00:00:43,000 --> 00:00:45,000
在中间的列表中，你可以看名字

18
00:00:45,000 --> 00:00:49,000
检查，如果米老鼠这个名字之前或之后。

19
00:00:49,000 --> 00:00:51,000
在第二列中的最后一个名称综观

20
00:00:51,000 --> 00:00:54,000
你会意识到M的米奇在J茉莉，

21
00:00:54,000 --> 00:00:57,000
所以，你会简单地忽略上半年的列表。

22
00:00:57,000 --> 00:00:59,000
然后，你可能会在顶部的最后一列

23
00:00:59,000 --> 00:01:02,000
，并认为它与长发姑娘开始。

24
00:01:02,000 --> 00:01:06,000
米奇之前，长发姑娘，看起来我们可以忽略的最后一列。

25
00:01:06,000 --> 00:01:08,000
继续搜索策略，你很快就会发现，米奇

26
00:01:08,000 --> 00:01:11,000
是在其它的名称列表中的第一个一半的

27
00:01:11,000 --> 00:01:14,000
终于找到米奇隐藏在梅林和米妮之间。

28
00:01:14,000 --> 00:01:17,000
>> 你刚才做的基本上是二进制搜索。

29
00:01:17,000 --> 00:01:22,000
正如这个名字所暗示的，它执行它的搜索策略，在一个二进制的问题。

30
00:01:22,000 --> 00:01:24,000
这是什么意思呢？

31
00:01:24,000 --> 00:01:27,000
那么，给出一个列表排序的项目，二进制搜索算法使得一个二进制的决定 - 

32
00:01:27,000 --> 00:01:33,000
左或右，大于或小于，之前或之后的字母顺序 - 在每一个点。

33
00:01:33,000 --> 00:01:35,000
现在，我们有一个名字伴随着本次搜索算法，

34
00:01:35,000 --> 00:01:38,000
让我们来看看另一个例子，但这次的列表排序的数字。

35
00:01:38,000 --> 00:01:43,000
说我们正在为数字144在此列表中的排序号码。

36
00:01:43,000 --> 00:01:46,000
就像以前一样，我们发现在中间的数字 - 

37
00:01:46,000 --> 00:01:50,000
在这种情况下是13  - 和看到，如果144是大于或小于13。

38
00:01:50,000 --> 00:01:54,000
因为它是明显大于13，我们可以忽略一切，这是13或更小

39
00:01:54,000 --> 00:01:57,000
只集中在剩下的一半。

40
00:01:57,000 --> 00:01:59,000
因为我们现在有一个偶数留下的物品，

41
00:01:59,000 --> 00:02:01,000
我们简单地选择一个数字，接近中间。

42
00:02:01,000 --> 00:02:03,000
在这种情况下，我们选择55。

43
00:02:03,000 --> 00:02:06,000
我们可以很容易地选择89。

44
00:02:06,000 --> 00:02:11,000
好吧。同样，144是大于55，所以我们去的权利。

45
00:02:11,000 --> 00:02:14,000
幸运的是，在未来的中间数是144，

46
00:02:14,000 --> 00:02:16,000
我们正在寻找的。

47
00:02:16,000 --> 00:02:21,000
因此，为了找到144使用二进制搜索，我们可以找到它的只有3个步骤。

48
00:02:21,000 --> 00:02:24,000
如果我们将使用线性搜索，将采取12个步骤。

49
00:02:24,000 --> 00:02:28,000
事实上，由于这个搜索方法的项目数减半

50
00:02:28,000 --> 00:02:31,000
它的每一步看，会发现它正在寻找的项目

51
00:02:31,000 --> 00:02:35,000
大约在日志列表中的项目的数目。

52
00:02:35,000 --> 00:02:37,000
现在，我们已经看到了2个例子，让我们一起来看看

53
00:02:37,000 --> 00:02:41,000
一个递归函数的伪代码实现二进制搜索。

54
00:02:41,000 --> 00:02:44,000
从顶部开始，我们可以看到，我们必须找到一个函数，它接受4个参数：

55
00:02:44,000 --> 00:02:47,000
键，阵列，最小和最大。

56
00:02:47,000 --> 00:02:51,000
最关键的是我们正在寻找的数字，所以144在前面的例子。

57
00:02:51,000 --> 00:02:54,000
数组是数字列表，我们正在寻找。

58
00:02:54,000 --> 00:02:57,000
min和max是最小和最大位置的指数，其中

59
00:02:57,000 --> 00:02:59,000
我们正在寻找。

60
00:02:59,000 --> 00:03:03,000
因此，当我们开始的时候，min将是零和最大将是最大的索引的数组。

61
00:03:03,000 --> 00:03:07,000
当我们缩小搜索范围，我们将更新的最小值和最大值

62
00:03:07,000 --> 00:03:10,000
的范围内，我们仍然往里看。

63
00:03:10,000 --> 00:03:12,000
>> 让我们先跳到最有趣的部分。

64
00:03:12,000 --> 00:03:14,000
我们做的第一件事是找到中点，

65
00:03:14,000 --> 00:03:19,000
该指数中间的最小值和最大值的数组，我们还在考虑。

66
00:03:19,000 --> 00:03:22,000
然后我们看一下，中点位置的值的数组

67
00:03:22,000 --> 00:03:25,000
看到，我们正在寻找的数字，如果是小于该键。

68
00:03:25,000 --> 00:03:27,000
如果在该位置上的数目比较少，

69
00:03:27,000 --> 00:03:31,000
那么它意味着关键是大于所有编号，以该位置的左侧的。

70
00:03:31,000 --> 00:03:33,000
因此，我们可以称之为二进制搜索功能，

71
00:03:33,000 --> 00:03:36,000
但这次更新的最小值和最大值参数只读取一半

72
00:03:36,000 --> 00:03:40,000
也就是大于或等于的值，我们刚刚看到的。

73
00:03:40,000 --> 00:03:44,000
在另一方面，如果该键的数目小于在当前阵列中点，

74
00:03:44,000 --> 00:03:47,000
我们想要去的左侧，而忽略所有的数字是更大的。

75
00:03:47,000 --> 00:03:52,000
同样，我们称之为二进制搜索，但这个时间范围内的最小值和最大值更新

76
00:03:52,000 --> 00:03:54,000
以仅包括下半部。

77
00:03:54,000 --> 00:03:57,000
如果阵列中的当前的中点处的值既不是

78
00:03:57,000 --> 00:04:01,000
大于也不小于键，那么它必须是相等的关键。

79
00:04:01,000 --> 00:04:05,000
因此，我们可以简单地返回当前的中点指数，我们就大功告成了。

80
00:04:05,000 --> 00:04:09,000
最后，这里此检查为的情况下，数字

81
00:04:09,000 --> 00:04:11,000
实际上不是在数组中的数字，我们正在寻找。

82
00:04:11,000 --> 00:04:14,000
如果在最大的范围内，我们正在寻找的指数

83
00:04:14,000 --> 00:04:17,000
高于最低要求是越来越少，这意味着我们已经走得太远了。

84
00:04:17,000 --> 00:04:20,000
由于数字输入数组中，我们返回-1

85
00:04:20,000 --> 00:04:24,000
表明，没有被发现。

86
00:04:24,000 --> 00:04:26,000
>> 您可能已经注意到了这个算法的工作，

87
00:04:26,000 --> 00:04:28,000
的号码列表进行排序。

88
00:04:28,000 --> 00:04:31,000
换句话说，我们只能找到144使用二进制搜索

89
00:04:31,000 --> 00:04:34,000
如果所有的数字都下令从最低到最高。

90
00:04:34,000 --> 00:04:38,000
如果不是这样的情况下，我们将无法排除一半的数字在每个步骤。

91
00:04:38,000 --> 00:04:40,000
因此，我们有2个选择。

92
00:04:40,000 --> 00:04:43,000
要么我们可以采取一个无序的列表，并使用二进制搜索，排序前，

93
00:04:43,000 --> 00:04:48,000
或者我们可以肯定，我们将号码添加到列表中的数字进行排序。

94
00:04:48,000 --> 00:04:50,000
因此，而不是排序的时候，我们要搜索​​，

95
00:04:50,000 --> 00:04:53,000
为什么不排序的列表，在任何时候都保持？

96
00:04:53,000 --> 00:04:57,000
>> 同时允许排序的方式，让一个数字列表

97
00:04:57,000 --> 00:04:59,000
一个添加或移动号码从这个名单

98
00:04:59,000 --> 00:05:02,000
是通过使用一种称为二叉搜索树。

99
00:05:02,000 --> 00:05:05,000
二叉搜索树是一种数据结构，有3个属性。

100
00:05:05,000 --> 00:05:09,000
首先，左子树中的任何节点只包含值小于

101
00:05:09,000 --> 00:05:11,000
或等于节点的值。

102
00:05:11,000 --> 00:05:15,000
其次，节点的右子树中包含的值大于

103
00:05:15,000 --> 00:05:17,000
或等于节点的值。

104
00:05:17,000 --> 00:05:20,000
以及最后，无论是左和右子树的所有节点

105
00:05:20,000 --> 00:05:23,000
二叉搜索树。

106
00:05:23,000 --> 00:05:26,000
让我们看一个例子，与我们之前使用的相同的号码。

107
00:05:26,000 --> 00:05:30,000
对于那些你从来没有见过计算机科学树前，

108
00:05:30,000 --> 00:05:34,000
首先，让我告诉你，计算机科学树是向下增长的。

109
00:05:34,000 --> 00:05:36,000
是的，不像你习惯的树木，

110
00:05:36,000 --> 00:05:38,000
计算机科学树的根是在顶部，

111
00:05:38,000 --> 00:05:41,000
和叶子都在底部。

112
00:05:41,000 --> 00:05:45,000
每个小方块被称为一个节点，节点由边缘彼此连接。

113
00:05:45,000 --> 00:05:48,000
因此，这棵树的根是一个节点值的值13，

114
00:05:48,000 --> 00:05:52,000
具有2个孩子的节点的值5和34。

115
00:05:52,000 --> 00:05:57,000
子树是树，形成整个树在第。

116
00:05:57,000 --> 00:06:03,000
>> 例如，左边的子树的节点3是建立的树由节点0，1和2。

117
00:06:03,000 --> 00:06:06,000
所以，如果我们回到一个二叉搜索树的性质，

118
00:06:06,000 --> 00:06:09,000
我们可以看到，在树中的每个节点符合所有3个属性，即，

119
00:06:09,000 --> 00:06:15,000
左子树仅包含节点的值小于或等于的值;

120
00:06:15,000 --> 00:06:16,000
所有节点的右子树

121
00:06:16,000 --> 00:06:19,000
只包含节点的值大于或等于值;

122
00:06:19,000 --> 00:06:25,000
左，右子树的所有节点也有二叉搜索树。

123
00:06:25,000 --> 00:06:28,000
虽然这棵树看起来不一样，这是一个有效的二叉搜索树

124
00:06:28,000 --> 00:06:30,000
对于同一组的数字。

125
00:06:30,000 --> 00:06:32,000
事实上，有许多可能的方式，你可以创建

126
00:06:32,000 --> 00:06:35,000
从这些数字的一个有效的二叉搜索树。

127
00:06:35,000 --> 00:06:38,000
好吧，让我们回到我们创建的第一个。

128
00:06:38,000 --> 00:06:40,000
所以，我们可以做什么与这些树呢？

129
00:06:40,000 --> 00:06:44,000
好了，我们可以很简单地找到的最低值和最高值。

130
00:06:44,000 --> 00:06:46,000
可以找到的最小值总是要在左边

131
00:06:46,000 --> 00:06:48,000
直到有没有更多的节点访问。

132
00:06:48,000 --> 00:06:53,000
相反，找到的最大的仅仅只是下山的权利在每个时间。

133
00:06:54,000 --> 00:06:56,000
>> 查找任何其他数目的最小值或最大值

134
00:06:56,000 --> 00:06:58,000
也很容易。

135
00:06:58,000 --> 00:07:00,000
假设我们正在寻找数89。

136
00:07:00,000 --> 00:07:03,000
我们简单地检查每个节点的值，向左或向右，

137
00:07:03,000 --> 00:07:06,000
根据节点的值是否小于或大于

138
00:07:06,000 --> 00:07:08,000
我们正在寻找的。

139
00:07:08,000 --> 00:07:11,000
所以，从13根，我们可以看到，89，

140
00:07:11,000 --> 00:07:13,000
所以我们去正确的。

141
00:07:13,000 --> 00:07:16,000
然后，我们看到了34节点，我们再次去正确的。

142
00:07:16,000 --> 00:07:20,000
89大于55，所以我们继续去合适。

143
00:07:20,000 --> 00:07:24,000
然后，我们来到了一个节点的值144，和去左边。

144
00:07:24,000 --> 00:07:26,000
你瞧，89是正确的。

145
00:07:26,000 --> 00:07:31,000
>> 我们可以做的另一件事，是打印出所有进行中序遍历。

146
00:07:31,000 --> 00:07:35,000
中序遍历是指打印任何事物的左子树

147
00:07:35,000 --> 00:07:37,000
随后由打印节点本身

148
00:07:37,000 --> 00:07:40,000
然后印刷一切在右子树。

149
00:07:40,000 --> 00:07:43,000
例如，让我们最喜欢的二叉搜索树

150
00:07:43,000 --> 00:07:46,000
的排序顺序打印出来的数字。

151
00:07:46,000 --> 00:07:49,000
首先，我们在13根的，但我们必须在打印前13打印出

152
00:07:49,000 --> 00:07:51,000
一切都在左子树。

153
00:07:51,000 --> 00:07:55,000
因此，我们转到5。我们仍然有更深入的倒在了树，直到我们找到了最左边的节点，

154
00:07:55,000 --> 00:07:57,000
这是零。

155
00:07:57,000 --> 00:08:00,000
印刷零后，我们回去到1，并打印了这一点。

156
00:08:00,000 --> 00:08:03,000
然后我们去的右子树，也就是2，打印了这一点。

157
00:08:03,000 --> 00:08:05,000
现在，我们已经完成了该子树，

158
00:08:05,000 --> 00:08:07,000
我们可以回去了3个，并把它打印出来。

159
00:08:07,000 --> 00:08:11,000
持续回升，我们打印5和8。

160
00:08:11,000 --> 00:08:13,000
现在，我们已经完成了整个左子树，

161
00:08:13,000 --> 00:08:17,000
我们可以打印出13个，并开始工作的右子树。

162
00:08:17,000 --> 00:08:21,000
我们跳了34，但我们必须在打印前34打印出其左子树。

163
00:08:21,000 --> 00:08:27,000
所以，我们打印出21，然后打印出34，访问右子树。

164
00:08:27,000 --> 00:08:31,000
由于55没有左子树，我们打印出来，并继续其右子树。

165
00:08:31,000 --> 00:08:36,000
144有一个左子树，所以我们打印出89，其次是144，

166
00:08:36,000 --> 00:08:39,000
233，最后最右边的节点。

167
00:08:39,000 --> 00:08:44,000
有你有它，所有的号码都打印出来，以便从最低到最高。

168
00:08:44,000 --> 00:08:47,000
>> 添加的树是什么，以及相对无痛的。

169
00:08:47,000 --> 00:08:51,000
我们要做的是确保我们按照二叉搜索树性能

170
00:08:51,000 --> 00:08:53,000
然后插入值有空间的地方。

171
00:08:53,000 --> 00:08:55,000
比方说，我们要插入的值是7。

172
00:08:55,000 --> 00:08:58,000
自7是小于13，我们去左边。

173
00:08:58,000 --> 00:09:01,000
但它大于5，所以我们遍历的权利。

174
00:09:01,000 --> 00:09:04,000
由于它是小于8和图8是一个叶节点，我们添加7至8的左子。

175
00:09:04,000 --> 00:09:09,000
瞧！我们已经添加了一个数字，我们的二叉搜索树。

176
00:09:09,000 --> 00:09:12,000
>> 如果我们可以添加的东西，我们最好是能够删除的东西。

177
00:09:12,000 --> 00:09:14,000
不幸的是，对我们来说，删除是一个有点复杂 - 

178
00:09:14,000 --> 00:09:16,000
虽然不大，但只是一点点。

179
00:09:16,000 --> 00:09:18,000
有3种不同的情况下，我们要考虑的

180
00:09:18,000 --> 00:09:21,000
删除元素时，从二叉搜索树。

181
00:09:21,000 --> 00:09:24,000
首先，最简单的情况是，该元素是一个叶节点。

182
00:09:24,000 --> 00:09:27,000
在这种情况下，我们简单地将其删除，并继续与我们的业务。

183
00:09:27,000 --> 00:09:30,000
假设我们要删除我们刚才添加的7。

184
00:09:30,000 --> 00:09:34,000
好了，我们只要找到它，删除它，就是这样。

185
00:09:35,000 --> 00:09:37,000
接下来的情况是，如果节点只有1名儿童。

186
00:09:37,000 --> 00:09:40,000
在这里，我们可以删除该节点，但我们首先必须确保

187
00:09:40,000 --> 00:09:42,000
连接的子树，现在是离开父母双亡的孤儿

188
00:09:42,000 --> 00:09:44,000
节点的父节点，我们只是删除了。

189
00:09:44,000 --> 00:09:47,000
假设我们从我们的树，要删除3。

190
00:09:47,000 --> 00:09:50,000
我们把该节点的子元素，并将它附加到节点的父节点。

191
00:09:50,000 --> 00:09:54,000
在这种情况下，我们现在将1到5。

192
00:09:54,000 --> 00:09:57,000
这没有问题，因为我们知道，根据二叉搜索树的性质，

193
00:09:57,000 --> 00:10:01,000
3的左子树，一切均小于5。

194
00:10:01,000 --> 00:10:05,000
现在，3的子树的照顾，我们可以将其删除。

195
00:10:05,000 --> 00:10:08,000
第三个和最后的情况是最复杂的。

196
00:10:08,000 --> 00:10:11,000
这是我们要删除的节点有2个孩子的情况下。

197
00:10:11,000 --> 00:10:15,000
为了做到这一点，我们首先要找到的节点有一个最大的价值，

198
00:10:15,000 --> 00:10:18,000
交换了两下，然后删除有问题的节点。

199
00:10:18,000 --> 00:10:22,000
请注意，节点，下一个最大的值不能有2个孩子

200
00:10:22,000 --> 00:10:26,000
因为它的左孩子为下一个最大的将是一个更好的人选。

201
00:10:26,000 --> 00:10:30,000
因此，删除一个节点有2个孩子，2个节点交换，

202
00:10:30,000 --> 00:10:33,000
然后删除处理由1 2上述规则。

203
00:10:33,000 --> 00:10:37,000
例如，让我们说，我们要删除的根节点，13。

204
00:10:37,000 --> 00:10:39,000
我们做的第一件事情是，我们发现在树中的下一个最大的价值

205
00:10:39,000 --> 00:10:41,000
其中，在这种情况下，为21。

206
00:10:41,000 --> 00:10:46,000
然后，我们交换的2个节点，13叶和21个中心组节点。

207
00:10:46,000 --> 00:10:49,000
现在，我们可以简单地删除13。

208
00:10:50,000 --> 00:10:53,000
>> 正如前面提到的，有许多可能的方法来进行有效的二叉搜索树。

209
00:10:53,000 --> 00:10:56,000
不幸的是，对我们来说，有些是比别人差。

210
00:10:56,000 --> 00:10:59,000
例如，会发生什么事时，我们建立了一个二叉搜索树

211
00:10:59,000 --> 00:11:01,000
从排序列表中的号码吗？

212
00:11:01,000 --> 00:11:04,000
所有的数字都只是添加到右边的每一步。

213
00:11:04,000 --> 00:11:06,000
当我们要搜索​​一个数字，

214
00:11:06,000 --> 00:11:08,000
我们别无选择，只有看的权利，在每一个步骤。

215
00:11:08,000 --> 00:11:11,000
这是不是比在所有的线性搜索。

216
00:11:11,000 --> 00:11:13,000
虽然我们不会掩盖他们在这里，还有其他更复杂的，

217
00:11:13,000 --> 00:11:16,000
数据结构，确保不会发生这种情况。

218
00:11:16,000 --> 00:11:18,000
然而，一个简单的事情可以做，以避免这种情况的是

219
00:11:18,000 --> 00:11:21,000
只是随机洗牌的输入值。

220
00:11:21,000 --> 00:11:26,000
这是极不可能的，一个偶然的机会洗牌的数字列表进行排序。

221
00:11:26,000 --> 00:11:29,000
如果是这样的话，赌场会不会留在企业长久的。

222
00:11:29,000 --> 00:11:31,000
>> 有你有它。

223
00:11:31,000 --> 00:11:34,000
您现在所了解的二进制搜索和二叉搜索树。

224
00:11:34,000 --> 00:11:36,000
我是帕特里克·施密德，这是CS50。

225
00:11:36,000 --> 00:11:38,000
[CS50.TV]

226
00:11:38,000 --> 00:11:43,000
一个明显的方法是将扫描列表... [哔]

227
00:11:43,000 --> 00:11:46,000
的项目数...是的

228
00:11:46,000 --> 00:11:50,000
[笑]

229
00:11:50,000 --> 00:11:55,000
...发布节点234 ... augh。

230
00:11:55,000 --> 00:11:58,000
>>耶！这是 -