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