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

2
00:00:13,300 --> 00:00:15,010
>> ROBボーデンは：こんにちは、私はロブだ。

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
そして、我々はあるint型の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
値の中間の値に等しいそうであれば、我々は
我々が見つけたので、trueを返すことができます

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
最後のパラメータが私たちのint型であることを覚えている
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
プラス私たちの元の値配列の1。

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
オリジナルを変更することをいとわ
values​​配列。

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
今、その種が過去である気づく2
パラメータがある値を、int型

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
それは、nのoを二乗である。

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
まあ、我々はすでにソートした場合は、最初の
その後、Nマイナス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
その後、我々は全体の上に行くつもりだ
配列には、再び第2探し

107
00:06:07,610 --> 00:06:10,410
最小要素、スティック、その
の2番目の位置にある

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
そこにいる場合よりも小さい任意の要素を参照してください。
我々は現在の通貨1

116
00:06:31,870 --> 00:06:33,900
最小値を考慮。

117
00:06:33,900 --> 00:06:38,840
>> だからここに、Jプラス1値 - それはです
我々は現在よりも少ない

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
から最小の要素であるべき
アレイ内の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