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

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Hallo, ich bin Rob.

3
00:00:15,010 --> 00:00:16,790
Wie verwenden wir eine binäre Suche?

4
00:00:16,790 --> 00:00:18,770
Lasst uns herausfinden.

5
00:00:18,770 --> 00:00:23,400
So ist zu beachten, dass diese Suche werden wir
rekursiv implementiert.

6
00:00:23,400 --> 00:00:27,470
Sie könnten auch binäre Suche zu implementieren
iterativ, also wenn du das getan hast,

7
00:00:27,470 --> 00:00:29,280
das ist völlig in Ordnung.

8
00:00:29,280 --> 00:00:32,820
>> Jetzt lassen Sie uns zuerst daran erinnern, was die
Parameter, die Suche werden sollen sein.

9
00:00:32,820 --> 00:00:36,120
Hier sehen wir int-Wert, der ist
soll der Wert der Benutzer sein

10
00:00:36,120 --> 00:00:37,320
für die Suche.

11
00:00:37,320 --> 00:00:40,800
Wir sehen die int-Werte-Array, das
ist das Array, in dem wir sind

12
00:00:40,800 --> 00:00:42,520
Suche nach Wert.

13
00:00:42,520 --> 00:00:45,602
Und wir sehen, int n, das ist,
die Länge der unser Angebot.

14
00:00:45,602 --> 00:00:47,410
>> Jetzt erste, was zuerst.

15
00:00:47,410 --> 00:00:51,350
Wir prüfen, ob n gleich 0 ist, in
welcher Fall kehren wir falsch.

16
00:00:51,350 --> 00:00:54,770
Das ist nur zu sagen, wenn wir ein leeres
Array-Wert ist eindeutig nicht in ein

17
00:00:54,770 --> 00:00:57,860
leeres Array, so können wir false zurück.

18
00:00:57,860 --> 00:01:01,250
>> Nun wollen wir eigentlich tun, um die binäre
Suche Teil der binären Suche.

19
00:01:01,250 --> 00:01:04,780
Also, wollen wir die Mitte finden
Element dieses Feldes.

20
00:01:04,780 --> 00:01:09,130
Hier, sagen wir, Mitte gleich n geteilt
von 2, da das mittlere Element ist

21
00:01:09,130 --> 00:01:12,240
gehen, um die Länge sein
unser Angebot durch 2 geteilt.

22
00:01:12,240 --> 00:01:15,040
Jetzt werden wir zu überprüfen, um zu sehen, ob die
Mittelelement gleich dem Wert sind wir

23
00:01:15,040 --> 00:01:16,160
für die Suche.

24
00:01:16,160 --> 00:01:21,030
Also, wenn Werte gleich mitten Wert, wir
kann true zurück, da fanden wir das

25
00:01:21,030 --> 00:01:22,810
Wert in unser Angebot.

26
00:01:22,810 --> 00:01:26,380
>> Aber wenn das nicht wahr war, jetzt
wir die rekursive tun müssen

27
00:01:26,380 --> 00:01:27,840
Schritt der binären Suche.

28
00:01:27,840 --> 00:01:30,450
Wir müssen entweder die Suche
links von der Anordnung oder der

29
00:01:30,450 --> 00:01:32,320
Mitte des Arrays.

30
00:01:32,320 --> 00:01:39,280
So, hier, sagen wir, wenn die Werte in Mitte ist
kleiner als der Wert, bedeutet, dass dieser Wert

31
00:01:39,280 --> 00:01:41,350
größer als der Mittel
des Arrays.

32
00:01:41,350 --> 00:01:45,790
So muss Wert auf der rechten Seite der sein
Element, das wir gerade sah.

33
00:01:45,790 --> 00:01:48,090
>> Also hier werden wir zu
Suche rekursiv.

34
00:01:48,090 --> 00:01:50,320
Und wir werden, was wir sind vorbei schauen
Um dies in einer Sekunde.

35
00:01:50,320 --> 00:01:53,440
Aber wir werden, um die Suche
rechts von dem mittleren Element.

36
00:01:53,440 --> 00:01:57,710
Und in dem anderen Fall, bedeutet das, dass
Wert kleiner als der Mitte der war

37
00:01:57,710 --> 00:02:00,660
Array, und so werden wir
nach links zu suchen.

38
00:02:00,660 --> 00:02:03,520
Jetzt wird die linke sein wird
ein bisschen einfacher, zu betrachten.

39
00:02:03,520 --> 00:02:07,770
So sehen wir hier, dass wir rekursiv
Aufruf suchen, wo die erste

40
00:02:07,770 --> 00:02:10,120
Argument ist wieder der Wert
wir suchen über.

41
00:02:10,120 --> 00:02:14,970
Das zweite Argument wird sein, die
Array, dass wir über die Suche.

42
00:02:14,970 --> 00:02:17,090
Und das letzte Element ist jetzt Mitte.

43
00:02:17,090 --> 00:02:21,650
Denken Sie daran, der letzte Parameter ist unser int
n, das ist also die Länge der unser Angebot.

44
00:02:21,650 --> 00:02:25,310
>> In der rekursiven Aufruf zu suchen, wir sind
jetzt sagen, daß die Länge der

45
00:02:25,310 --> 00:02:27,230
Array ist Mitte.

46
00:02:27,230 --> 00:02:32,900
Also, wenn unser Angebot war von der Größe 20 und wir
bei Index 10 gesucht, da Mitte ist

47
00:02:32,900 --> 00:02:36,930
20 geteilt durch 2, bedeutet, dass wir
indem 10 als neuer

48
00:02:36,930 --> 00:02:38,300
Länge unseres Arrays.

49
00:02:38,300 --> 00:02:41,910
Denken Sie daran, dass, wenn Sie ein Array haben
der Länge 10, bedeutet, dass die gültige

50
00:02:41,910 --> 00:02:45,450
Elemente sind in den Indizes 0 bis 9 an.

51
00:02:45,450 --> 00:02:50,120
Also das ist genau das, was wir wollen
geben unsere aktualisierte Array - die linke

52
00:02:50,120 --> 00:02:53,010
Anordnung aus dem mittleren Element.

53
00:02:53,010 --> 00:02:55,710
>> Also, Blick nach rechts ist
ein bisschen schwieriger.

54
00:02:55,710 --> 00:03:00,170
Jetzt lassen Sie uns zuerst betrachten die Länge
der Anordnung auf der rechten Seite der

55
00:03:00,170 --> 00:03:01,240
Mittelelement.

56
00:03:01,240 --> 00:03:08,390
Also, wenn unser Angebot war der Größe n, dann ist die
neue Array der Größe n minus sein

57
00:03:08,390 --> 00:03:10,140
Mitte minus 1.

58
00:03:10,140 --> 00:03:12,530
Also, lasst uns von n minus Mitte denken.

59
00:03:12,530 --> 00:03:18,710
>> Auch wenn das Array waren von der Größe 20 und
wir durch 2 teilen, um die Mitte zu bekommen,

60
00:03:18,710 --> 00:03:23,540
so ist die Mitte 10 ist, dann n minus Mitte
wird uns geben, 10, also 10

61
00:03:23,540 --> 00:03:25,330
Elemente auf der rechten Mitte.

62
00:03:25,330 --> 00:03:27,780
Aber wir haben auch diesen minus
1, da wir nicht wollen,

63
00:03:27,780 --> 00:03:29,700
gehören die Mitte selber.

64
00:03:29,700 --> 00:03:34,190
So n minus Mitte minus 1 gibt uns die
Gesamtzahl der Elemente rechts

65
00:03:34,190 --> 00:03:36,800
der mittlere Index im Array.

66
00:03:36,800 --> 00:03:41,870
>> Jetzt ist hier zu beachten, dass der mittlere
Parameter ist die Array-Werte.

67
00:03:41,870 --> 00:03:46,180
So, hier übergeben wir ein
aktualisierten Werte Array.

68
00:03:46,180 --> 00:03:50,930
Diese Werte sowie mittlere plus 1 ist
eigentlich sagt rekursiv

69
00:03:50,930 --> 00:03:56,460
Suche, vorbei in einem neuen Array, wo
dass neue Array beginnt in der Mitte

70
00:03:56,460 --> 00:03:59,370
plus eine unserer ursprünglichen Werte-Array.

71
00:03:59,370 --> 00:04:05,400
>> Eine alternative Syntax für die, jetzt,
Sie begonnen haben, um Zeiger zu sehen, ist

72
00:04:05,400 --> 00:04:10,170
Kaufmanns-Werte Mitte plus 1.

73
00:04:10,170 --> 00:04:17,149
Also, packen Sie die Adresse der Mitte
und ein Element der Werte.

74
00:04:17,149 --> 00:04:23,690
>> Nun, wenn Sie nicht zufrieden waren
Ändern von Arrays wie die, die Sie

75
00:04:23,690 --> 00:04:28,900
hätte auch dies mit umgesetzt
eine rekursive Hilfsfunktion, wo

76
00:04:28,900 --> 00:04:31,680
dass Hilfsfunktion nimmt
mehr Argumente.

77
00:04:31,680 --> 00:04:36,610
Anstatt also nur der Wert, desto
Anordnung und der Größe des Arrays,

78
00:04:36,610 --> 00:04:42,315
die Hilfsfunktion könnte länger dauern
Argumente, einschließlich der unteren Index

79
00:04:42,315 --> 00:04:45,280
Sie würde etwa in der Anordnung Pflege
und der obere Index, den Sie kümmern

80
00:04:45,280 --> 00:04:46,300
über die Anordnung.

81
00:04:46,300 --> 00:04:49,770
>> Und so die Verfolgung der beiden unteren
Index und der obere Index, brauchen Sie nicht

82
00:04:49,770 --> 00:04:52,780
brauchen, um überhaupt das ändern
Originalwerte Array.

83
00:04:52,780 --> 00:04:56,390
Sie können einfach weiter
Verwenden Sie die Werte Array.

84
00:04:56,390 --> 00:04:59,540
Aber hier, bemerken wir einen Helfer brauchen nicht
funktionieren, solange wir sind

85
00:04:59,540 --> 00:05:01,760
bereit, um die ursprüngliche ändern
Werte Array.

86
00:05:01,760 --> 00:05:05,020
Wir sind bereit, übergeben
eine aktualisierte Werte.

87
00:05:05,020 --> 00:05:09,140
>> Nun, wir können nicht über binäre Suche
ein Array, das unsortiert ist.

88
00:05:09,140 --> 00:05:12,220
Also, lassen Sie uns diese aussortiert.

89
00:05:12,220 --> 00:05:17,650
Nun bemerken, dass Art ist seit zwei
Parameter int-Werte, was ist das

90
00:05:17,650 --> 00:05:21,110
Array, das wir sortieren und int n,
die die Länge des Arrays ist, dass

91
00:05:21,110 --> 00:05:22,250
wir sortieren.

92
00:05:22,250 --> 00:05:24,840
So, hier umsetzen wollen wir
ein Sortieralgorithmus

93
00:05:24,840 --> 00:05:26,690
das ist o n quadriert.

94
00:05:26,690 --> 00:05:30,560
Sie könnten Bubble-Sort, Auswahl wählen
Art oder Insertion sortieren oder

95
00:05:30,560 --> 00:05:32,670
eine andere Art haben wir nicht
in der Klasse gesehen.

96
00:05:32,670 --> 00:05:36,380
Aber hier werden wir zu gehen
Auswahl Art verwenden.

97
00:05:36,380 --> 00:05:40,030
>> Also, wir gehen zu durchlaufen
über die gesamte Anordnung.

98
00:05:40,030 --> 00:05:44,360
Nun, hier sehen wir, dass wir die Iteration
von 0 bis n minus 1 ist.

99
00:05:44,360 --> 00:05:45,990
Warum nicht den ganzen Weg bis zu n?

100
00:05:45,990 --> 00:05:49,320
Nun, wenn wir bereits sortiert haben die erste
n minus 1 Elemente, dann die

101
00:05:49,320 --> 00:05:54,420
letzte Element, was muss schon sein
an der richtigen Stelle, so dass die Sortierung über

102
00:05:54,420 --> 00:05:56,520
das gesamte Array.

103
00:05:56,520 --> 00:05:58,770
>> Nun, daran erinnern, wie Auswahl
Art funktioniert.

104
00:05:58,770 --> 00:06:01,950
Wir werden über das gesamte Array gehen
Suche nach der Minimalwert

105
00:06:01,950 --> 00:06:04,480
und das Array-Stick,
am Anfang.

106
00:06:04,480 --> 00:06:07,610
Dann werden wir über die gesamte gehen
Array wieder auf der Suche nach der zweiten

107
00:06:07,610 --> 00:06:10,410
kleinste Element, und Stick,
in der zweiten Position, in der

108
00:06:10,410 --> 00:06:12,100
Array, und so weiter.

109
00:06:12,100 --> 00:06:14,330
Also, das ist, was dieser tut.

110
00:06:14,330 --> 00:06:17,290
>> Hier sehen wir, dass wir
Einstellung der aktuellen Mindest

111
00:06:17,290 --> 00:06:20,030
Wert des i-ten Index.

112
00:06:20,030 --> 00:06:23,160
Also auf der ersten Iteration, wir gehen
zu prüfen, der Minimalwert zu sein

113
00:06:23,160 --> 00:06:25,030
der Beginn unserer Array.

114
00:06:25,030 --> 00:06:28,500
Dann werden wir über die laufen
Rest der Anordnung, zu überprüfen,

115
00:06:28,500 --> 00:06:31,870
sehen, ob es irgendwelche Elemente kleiner als
die, die wir sind momentan

116
00:06:31,870 --> 00:06:33,900
unter Berücksichtigung der Mindest.

117
00:06:33,900 --> 00:06:38,840
>> So, hier sind Werte j plus ein - das ist
weniger als das, was wir derzeit

118
00:06:38,840 --> 00:06:40,380
unter Berücksichtigung der Mindest.

119
00:06:40,380 --> 00:06:42,940
Dann werden wir aktualisieren, was
wir denken, ist das Minimum, um

120
00:06:42,940 --> 00:06:44,640
Index j plus 1.

121
00:06:44,640 --> 00:06:48,540
Also, dass über die gesamte Array
und nach dieser for-Schleife, Mindest

122
00:06:48,540 --> 00:06:53,160
sollte die Mindest Element sein
der i-ten Position in der Anordnung.

123
00:06:53,160 --> 00:06:57,350
>> Sobald wir das, wir tauschen kann die
Minimalwert in der i-ten Position

124
00:06:57,350 --> 00:06:58,230
in der Anordnung.

125
00:06:58,230 --> 00:07:00,130
Also das ist nur ein Standard-Swap.

126
00:07:00,130 --> 00:07:03,940
Wir speichern in einem temporären Wert -
der i-te Wert in der Anordnung -

127
00:07:03,940 --> 00:07:08,460
in die i-te Wert in der Anordnung stellen die
Minimalwert, der es angehört,

128
00:07:08,460 --> 00:07:13,580
und dann wieder speichern, in denen die
aktuelle Mindestwert verwendet, um die sein

129
00:07:13,580 --> 00:07:16,460
i-te Wert in der Matrix, so
dass wir nicht verlieren.

130
00:07:16,460 --> 00:07:20,510
>> So, das weiter auf
die nächste Iteration.

131
00:07:20,510 --> 00:07:23,480
Wir werden die Suche nach dem zweiten
Minimalwert und legen Sie, dass in der

132
00:07:23,480 --> 00:07:24,590
zweite Position.

133
00:07:24,590 --> 00:07:27,440
Auf der dritten Iteration, wir suchen
der dritte Minimalwert und Einsatz

134
00:07:27,440 --> 00:07:31,550
dass in der dritten Position, und so
auf, bis wir eine sortierte Array.

135
00:07:31,550 --> 00:07:33,820
Mein Name ist Rob, und dies
Auswahl Art war.

136
00:07:33,820 --> 00:07:39,456