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

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Szia, én vagyok Rob.

3
00:00:15,010 --> 00:00:16,790
Hogy mi foglalkoztat egy bináris keresést?

4
00:00:16,790 --> 00:00:18,770
Nézzük meg.

5
00:00:18,770 --> 00:00:23,400
Tehát, vegye figyelembe, hogy ez a keresés megyünk
végrehajtása rekurzívan.

6
00:00:23,400 --> 00:00:27,470
Te is végre bináris keresés
iteratív módon, tehát, ha azt tenné,

7
00:00:27,470 --> 00:00:29,280
ez tökéletesen megfelel.

8
00:00:29,280 --> 00:00:32,820
>> Most először, ne felejtsük el, amit a
paramétereket a keresés célja, hogy.

9
00:00:32,820 --> 00:00:36,120
Itt látjuk int érték, ami
állítólag az érték a felhasználó

10
00:00:36,120 --> 00:00:37,320
keres.

11
00:00:37,320 --> 00:00:40,800
Látjuk a int értékeket tömb, amely
az a tömb, amelyben vagyunk

12
00:00:40,800 --> 00:00:42,520
keresett értéket.

13
00:00:42,520 --> 00:00:45,602
És azt látjuk, int n, ami
a hossza a tömb.

14
00:00:45,602 --> 00:00:47,410
>> Nos, az első dolog az első.

15
00:00:47,410 --> 00:00:51,350
Ellenőrizzük, hogy ha n értéke 0, a
mely esetben return false.

16
00:00:51,350 --> 00:00:54,770
Ez csak azt mondom, ha van egy üres
tömb értéke nyilvánvalóan nem egy

17
00:00:54,770 --> 00:00:57,860
üres tömböt, így is vissza hamis.

18
00:00:57,860 --> 00:01:01,250
>> Most valóban szeretné ezt a bináris
keresés része a bináris keresés.

19
00:01:01,250 --> 00:01:04,780
Tehát, meg akarjuk találni a közepén
eleme a tömb.

20
00:01:04,780 --> 00:01:09,130
Itt mondjuk közepes értéke n megosztott
2-vel, mivel a középső elem

21
00:01:09,130 --> 00:01:12,240
lesz a hossza
a tömb osztva 2-vel.

22
00:01:12,240 --> 00:01:15,040
Most megyünk, hogy ellenőrizze, hogy a
középső elem megegyezik az értéket vagyunk

23
00:01:15,040 --> 00:01:16,160
keres.

24
00:01:16,160 --> 00:01:21,030
Tehát, ha értéke közepén egyenlő értéket, akkor
Visszatérhet igaz, mert megtaláltuk a

25
00:01:21,030 --> 00:01:22,810
érték a tömbben.

26
00:01:22,810 --> 00:01:26,380
>> De ha ez nem volt igaz, most
meg kell csinálni a rekurzív

27
00:01:26,380 --> 00:01:27,840
lépése bináris keresés.

28
00:01:27,840 --> 00:01:30,450
Meg kell keresni, hogy vagy a
elhagyta a tömb vagy a

29
00:01:30,450 --> 00:01:32,320
közepén a tömb.

30
00:01:32,320 --> 00:01:39,280
Tehát itt, azt mondják, ha értékeket középen
kisebb érték, azt jelenti, hogy értéke

31
00:01:39,280 --> 00:01:41,350
nagyobb volt, mint a középső
a tömb.

32
00:01:41,350 --> 00:01:45,790
Így érték kell, hogy legyen, hogy a jobb oldalon a
elem, hogy csak nézett.

33
00:01:45,790 --> 00:01:48,090
>> Tehát itt, megyünk
keresés rekurzívan.

34
00:01:48,090 --> 00:01:50,320
És nézzük meg, amit mi halad
ehhez a második.

35
00:01:50,320 --> 00:01:53,440
De fogunk keresni, hogy a
jobb a középső elem.

36
00:01:53,440 --> 00:01:57,710
És a másik esetben, ami azt jelenti, hogy a
értéke kisebb volt, mint a közepén, a

37
00:01:57,710 --> 00:02:00,660
tömb, és így megyünk
keresni a bal oldalon.

38
00:02:00,660 --> 00:02:03,520
Most a bal oldali lesz
egy kicsit könnyebb nézni.

39
00:02:03,520 --> 00:02:07,770
Tehát azt látjuk, hogy itt vagyunk rekurzívan
hívja kereső, ahol az első

40
00:02:07,770 --> 00:02:10,120
érv ismét az érték
keresünk vége.

41
00:02:10,120 --> 00:02:14,970
A második érv lesz a
tömb kerestük vége.

42
00:02:14,970 --> 00:02:17,090
És az utolsó elem most közepén.

43
00:02:17,090 --> 00:02:21,650
Ne feledje, az utolsó paraméter az int
n, hogy ez a hossza a tömb.

44
00:02:21,650 --> 00:02:25,310
>> A rekurzív hívás keresni, vagyunk
most azt mondja, hogy a hossza a

45
00:02:25,310 --> 00:02:27,230
tömb közepén.

46
00:02:27,230 --> 00:02:32,900
Tehát, ha a tömb volt a mérete 20 és
keresni az index 10, mivel a középen

47
00:02:32,900 --> 00:02:36,930
20 osztva 2, ez azt jelenti, nem vagyunk
10 halad, mint az új

48
00:02:36,930 --> 00:02:38,300
hossza a tömb.

49
00:02:38,300 --> 00:02:41,910
Ne feledje, hogy ha van egy tömb
A hossz 10, azt jelenti, hogy az érvényes

50
00:02:41,910 --> 00:02:45,450
vannak-indexek 0-tól 9.

51
00:02:45,450 --> 00:02:50,120
Tehát pontosan ez az, amit akarunk
adja meg a frissített tömb - a baloldali

52
00:02:50,120 --> 00:02:53,010
tömb a középső elem.

53
00:02:53,010 --> 00:02:55,710
>> Tehát, akik a jog
egy kicsit nehezebb.

54
00:02:55,710 --> 00:03:00,170
Most először, nézzük meg a hosszát
a tömb jobbra a

55
00:03:00,170 --> 00:03:01,240
középső elem.

56
00:03:01,240 --> 00:03:08,390
Tehát, ha a tömb volt méretű n, akkor a
új tömb lesz n méretű mínusz

57
00:03:08,390 --> 00:03:10,140
közepén mínusz 1.

58
00:03:10,140 --> 00:03:12,530
Szóval, most gondolj n mínusz közepén.

59
00:03:12,530 --> 00:03:18,710
>> Ismét, ha a tömb mérete 20 voltak, és
osztunk 2, hogy a közép-,

60
00:03:18,710 --> 00:03:23,540
így a középső 10, akkor n mínusz közepén
megy, nekünk 10, azaz 10

61
00:03:23,540 --> 00:03:25,330
elemek jobbra közepén.

62
00:03:25,330 --> 00:03:27,780
De mi is ez a mínusz
1., mert nem akarjuk, hogy

63
00:03:27,780 --> 00:03:29,700
többek között a középső is.

64
00:03:29,700 --> 00:03:34,190
Tehát n mínusz közepén mínusz 1 megadja a
száma elemek megfelelő

65
00:03:34,190 --> 00:03:36,800
a középső index a tömbben.

66
00:03:36,800 --> 00:03:41,870
>> Most itt van, ne feledje, hogy a középső
paraméter az értékeket tömb.

67
00:03:41,870 --> 00:03:46,180
Tehát itt, most leadott
frissített értékeket tömb.

68
00:03:46,180 --> 00:03:50,930
Ez az érték, plusz középen plusz 1
valójában mondani rekurzív hívás

69
00:03:50,930 --> 00:03:56,460
keresés, átadva az új tömb, ahol a
hogy az új tömb közepén kezdődik

70
00:03:56,460 --> 00:03:59,370
és az egyik az eredeti értékek tömb.

71
00:03:59,370 --> 00:04:05,400
>> Egy alternatív szintaxist, hogy most, hogy
már kezdett látni mutatók, az

72
00:04:05,400 --> 00:04:10,170
jel értékek közepes plusz 1.

73
00:04:10,170 --> 00:04:17,149
Szóval, fogd a címet a középső
plusz egy eleme értékeket.

74
00:04:17,149 --> 00:04:23,690
>> Most, ha nem kényelmes
módosítása egy tömböt, mint, hogy

75
00:04:23,690 --> 00:04:28,900
is hajtották végre ezt a
rekurzív segítő funkció, ahol a

76
00:04:28,900 --> 00:04:31,680
hogy a segítő függvény
több paramétert.

77
00:04:31,680 --> 00:04:36,610
Tehát ahelyett, hogy csak az érték, annál
tömb, és a mérete a tömb,

78
00:04:36,610 --> 00:04:42,315
A segítő funkció is, hogy több
érvek, beleértve az alsó index

79
00:04:42,315 --> 00:04:45,280
hogy Ön is törődnek a tömbben
és a felső index, hogy érdekel

80
00:04:45,280 --> 00:04:46,300
a tömb.

81
00:04:46,300 --> 00:04:49,770
>> És így nyomon követése mind az alsó
index és a felső index, akkor nem

82
00:04:49,770 --> 00:04:52,780
kell, hogy valaha is módosítani a
eredeti értékeket tömb.

83
00:04:52,780 --> 00:04:56,390
Tudod csak tovább
Az opció értéke tömb.

84
00:04:56,390 --> 00:04:59,540
De itt, észre nem kell egy segítő
működik, amíg mi vagyunk

85
00:04:59,540 --> 00:05:01,760
hajlandó, hogy módosítja az eredeti
értékeket tömb.

86
00:05:01,760 --> 00:05:05,020
Vagyunk hajlandóak átadni
frissített értékeket.

87
00:05:05,020 --> 00:05:09,140
>> Nos, nem tudjuk bináris keresés vége
egy tömböt, ami rendezetlen.

88
00:05:09,140 --> 00:05:12,220
Szóval, most e válogatni ki.

89
00:05:12,220 --> 00:05:17,650
Most veszi észre, hogy a fajta az elmúlt két
int paraméterek értékeit, amely a

90
00:05:17,650 --> 00:05:21,110
array, hogy mi válogatás, és int n,
amely a hossza a tömb

91
00:05:21,110 --> 00:05:22,250
mi válogatás.

92
00:05:22,250 --> 00:05:24,840
Szóval, itt akarunk végrehajtani
a rendezési algoritmus

93
00:05:24,840 --> 00:05:26,690
hogy o n a négyzeten.

94
00:05:26,690 --> 00:05:30,560
Lehet választani bubble sort, a kiválasztás
sort, vagy beillesztés sort, vagy

95
00:05:30,560 --> 00:05:32,670
valamilyen más fajta mi nem
látott az osztályban.

96
00:05:32,670 --> 00:05:36,380
De itt, fogunk
használata kiválasztás sort.

97
00:05:36,380 --> 00:05:40,030
>> Így megyünk iterációkhoz
az egész tömb.

98
00:05:40,030 --> 00:05:44,360
Nos, itt azt látjuk, hogy mi iterációjával
n 0-tól mínusz 1.

99
00:05:44,360 --> 00:05:45,990
Miért nem egészen n-ig?

100
00:05:45,990 --> 00:05:49,320
Nos, ha már sorrendje az első
n mínusz 1 elem, akkor az

101
00:05:49,320 --> 00:05:54,420
utolsó elem, amit meg már
a megfelelő helyre, így a válogatás több mint

102
00:05:54,420 --> 00:05:56,520
az egész tömböt.

103
00:05:56,520 --> 00:05:58,770
>> Nos, emlékszem, milyen kiválasztás
sort működik.

104
00:05:58,770 --> 00:06:01,950
Fogunk menni az egész tömb
keresi a minimum érték

105
00:06:01,950 --> 00:06:04,480
a tömb és a botot, hogy
az elején.

106
00:06:04,480 --> 00:06:07,610
Ezután fogunk menni az egész
array ismét keresi a második

107
00:06:07,610 --> 00:06:10,410
legkisebb elem, és a bot, hogy
a második helyzetben a

108
00:06:10,410 --> 00:06:12,100
tömb, és így tovább.

109
00:06:12,100 --> 00:06:14,330
Nos, ez az, amit ez csinál.

110
00:06:14,330 --> 00:06:17,290
>> Itt látjuk, hogy mi vagyunk
beállítása a jelenlegi minimális

111
00:06:17,290 --> 00:06:20,030
értéke az i-edik index.

112
00:06:20,030 --> 00:06:23,160
Tehát az első iteráció, megyünk
hogy fontolja meg a minimális értéket, hogy

113
00:06:23,160 --> 00:06:25,030
kezdetén a tömb.

114
00:06:25,030 --> 00:06:28,500
Akkor fogunk végighaladni a
fennmaradó tömb, ellenőrzi, hogy

115
00:06:28,500 --> 00:06:31,870
nézd meg, van olyan elem kisebb
Az egyik, hogy mi vagyunk jelenleg

116
00:06:31,870 --> 00:06:33,900
figyelembe véve a minimum.

117
00:06:33,900 --> 00:06:38,840
>> Tehát itt, értékek j plusz egy -, hogy
kevesebb, mint amit mi jelenleg

118
00:06:38,840 --> 00:06:40,380
figyelembe véve a minimum.

119
00:06:40,380 --> 00:06:42,940
Ezután fogjuk frissíteni, milyen
azt hiszem, az a minimum, hogy

120
00:06:42,940 --> 00:06:44,640
index j plusz 1.

121
00:06:44,640 --> 00:06:48,540
Szóval, hogy az egész tömböt,
és miután ez a for ciklus, minimum

122
00:06:48,540 --> 00:06:53,160
minimális legyen az elem
az i-edik pozíció a tömbben.

123
00:06:53,160 --> 00:06:57,350
>> Ha megvan, hogy mi lehet cserélni a
minimum értéket az i-edik pozíció

124
00:06:57,350 --> 00:06:58,230
a tömbben.

125
00:06:58,230 --> 00:07:00,130
Tehát ez csak egy szokásos csere.

126
00:07:00,130 --> 00:07:03,940
Mi tárolja ideiglenes érték -
az i-edik értékét a tömbben -

127
00:07:03,940 --> 00:07:08,460
helyezve az i-edik értékét az a tömbben
minimális érték tartozik, ott,

128
00:07:08,460 --> 00:07:13,580
majd tárolja vissza, ahol a
jelenlegi minimális érték szokott lenni a

129
00:07:13,580 --> 00:07:16,460
i-edik értékét a tömbben, így
hogy nem vesztette el.

130
00:07:16,460 --> 00:07:20,510
>> Úgy, hogy folytatódik
A következő iteráció.

131
00:07:20,510 --> 00:07:23,480
Fogunk kezdeni a második
minimális érték, és helyezze, hogy a

132
00:07:23,480 --> 00:07:24,590
második helyzetben.

133
00:07:24,590 --> 00:07:27,440
A harmadik ismétlés, akkor keresni
A harmadik legkisebb érték és betét

134
00:07:27,440 --> 00:07:31,550
hogy a harmadik helyre, és így
, amíg van egy rendezett tömbben.

135
00:07:31,550 --> 00:07:33,820
A nevem Rob, és ez a
volt választás sort.

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