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

2
00:00:13,300 --> 00:00:15,010
>> ROB Bowden: Bok, ja sam Rob.

3
00:00:15,010 --> 00:00:16,790
Kako ćemo zaposliti binarno pretraživanje?

4
00:00:16,790 --> 00:00:18,770
Idemo saznati.

5
00:00:18,770 --> 00:00:23,400
Dakle, imajte na umu da je ta potraga idemo
provesti rekurzivno.

6
00:00:23,400 --> 00:00:27,470
Također se može provesti binarni pretragu
iterativno, pa ako je to učinio,

7
00:00:27,470 --> 00:00:29,280
to je savršeno u redu.

8
00:00:29,280 --> 00:00:32,820
>> Sada prvi put, sjetimo se što
Parametri za pretragu su trebali biti.

9
00:00:32,820 --> 00:00:36,120
Ovdje vidimo int vrijednosti, što je
bi trebala biti vrijednost korisnik

10
00:00:36,120 --> 00:00:37,320
u potrazi za.

11
00:00:37,320 --> 00:00:40,800
Vidimo niz int vrijednosti, koje
je niz u kojem smo

12
00:00:40,800 --> 00:00:42,520
u potrazi za vrijednosti.

13
00:00:42,520 --> 00:00:45,602
I vidimo int n, što je
Duljina našeg polja.

14
00:00:45,602 --> 00:00:47,410
>> Sada, prva stvar na prvom mjestu.

15
00:00:47,410 --> 00:00:51,350
Provjerili smo da li je n = 0, u
čemu smo se vratili lažna.

16
00:00:51,350 --> 00:00:54,770
To samo govori da se moramo prazna
polje, vrijednost očito nije u

17
00:00:54,770 --> 00:00:57,860
prazno polje, pa smo se vratili lažna.

18
00:00:57,860 --> 00:01:01,250
>> Sada, mi zapravo želite učiniti binarni
traži dio binarnog pretraživanja.

19
00:01:01,250 --> 00:01:04,780
Dakle, želimo pronaći sredinu
element tog niza.

20
00:01:04,780 --> 00:01:09,130
Evo, mi kažemo middle jednaka n podijeljeni
za 2, jer srednji element

21
00:01:09,130 --> 00:01:12,240
će biti duljina
naša polja podijeljena dva.

22
00:01:12,240 --> 00:01:15,040
Sada ćemo provjeriti je li
Srednji element koji je jednak vrijednosti koju ste

23
00:01:15,040 --> 00:01:16,160
u potrazi za.

24
00:01:16,160 --> 00:01:21,030
Dakle, ako vrijednosti srednje jednaka vrijednosti, mi
može vratiti točno jer smo otkrili

25
00:01:21,030 --> 00:01:22,810
vrijednost u našem polju.

26
00:01:22,810 --> 00:01:26,380
>> Ali ako to nije bila istina, sada
moramo učiniti rekurzivna

27
00:01:26,380 --> 00:01:27,840
korak binarnog pretraživanja.

28
00:01:27,840 --> 00:01:30,450
Moramo tražiti ni
lijevo od niza ili

29
00:01:30,450 --> 00:01:32,320
usred polja.

30
00:01:32,320 --> 00:01:39,280
Pa evo, recimo, ako vrijednosti u sredini je
manja od vrijednosti, što znači da je vrijednost

31
00:01:39,280 --> 00:01:41,350
bio veći od sredine
od niza.

32
00:01:41,350 --> 00:01:45,790
Dakle, vrijednost mora biti na desnoj strani
element koji smo upravo pogledao.

33
00:01:45,790 --> 00:01:48,090
>> Dakle, ovdje, idemo u
traži rekurzivno.

34
00:01:48,090 --> 00:01:50,320
I mi ćemo pogledati što smo prolazu
to u sekundi.

35
00:01:50,320 --> 00:01:53,440
Ali ćemo tražiti da se
Pravo srednjeg elementa.

36
00:01:53,440 --> 00:01:57,710
I u drugom slučaju, to znači da
vrijednost je manja od polovice

37
00:01:57,710 --> 00:02:00,660
polje, pa idemo
u potrazi za lijevo.

38
00:02:00,660 --> 00:02:03,520
Sada, lijevo će biti
malo lakše pogledati.

39
00:02:03,520 --> 00:02:07,770
Dakle, ovdje vidimo da smo rekurzivno
nazivajući pretragu, gdje je prvi

40
00:02:07,770 --> 00:02:10,120
Argument je, opet, vrijednost
da tražimo više.

41
00:02:10,120 --> 00:02:14,970
Drugi argument će biti
Niz koji smo tražili više.

42
00:02:14,970 --> 00:02:17,090
I posljednji element koji je sada srednji.

43
00:02:17,090 --> 00:02:21,650
Sjeti se zadnji parametar je naš int
n, tako da je dužina naše polje.

44
00:02:21,650 --> 00:02:25,310
>> U rekurzivni poziv za pretraživanje, mi smo
Sada kaže da je duljina

45
00:02:25,310 --> 00:02:27,230
Niz je srednji.

46
00:02:27,230 --> 00:02:32,900
Dakle, ako naše polje je veličine 20 i mi
Tražili indeksa 10, budući da je srednji

47
00:02:32,900 --> 00:02:36,930
20 podijeljeno s dva, to znači da smo
prolazi 10 kao nova

48
00:02:36,930 --> 00:02:38,300
duljina naše polje.

49
00:02:38,300 --> 00:02:41,910
Zapamtite da kada imate niz
duljine 10, to znači da vrijedi

50
00:02:41,910 --> 00:02:45,450
elementi su indeksa 0 do 9.

51
00:02:45,450 --> 00:02:50,120
Dakle, to je upravo ono što želimo
odrediti našu obnovljeno niz - lijevi

52
00:02:50,120 --> 00:02:53,010
Niz od srednjeg elementa.

53
00:02:53,010 --> 00:02:55,710
>> Dakle, u potrazi za pravom je
malo teže.

54
00:02:55,710 --> 00:03:00,170
Sada je prvi, neka je uzeti u obzir duljinu
od niza s desne strane

55
00:03:00,170 --> 00:03:01,240
Srednji elementa.

56
00:03:01,240 --> 00:03:08,390
Dakle, ako je naš niz veličine n, tada
Nova polje će biti veličine n minusu

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

58
00:03:10,140 --> 00:03:12,530
Dakle, neka je razmišljati o n minus sredini.

59
00:03:12,530 --> 00:03:18,710
>> Opet, ako je niz su veličine 20 i
podijelimo sa 2 da se u sredini,

60
00:03:18,710 --> 00:03:23,540
pa srednji je 10, a zatim n minus srednje
će nam dati 10, pa 10

61
00:03:23,540 --> 00:03:25,330
elementi na desnoj strani sredini.

62
00:03:25,330 --> 00:03:27,780
No, imamo i ovaj minus
1, jer mi ne želimo da se

63
00:03:27,780 --> 00:03:29,700
uključuju samu sredinu.

64
00:03:29,700 --> 00:03:34,190
Dakle n minus srednji minus 1 nam daje
ukupni broj elemenata na desnoj strani

65
00:03:34,190 --> 00:03:36,800
srednjeg indeksa u nizu.

66
00:03:36,800 --> 00:03:41,870
>> Sada ovdje, ne zaboravite da je srednji
parametar je polje vrijednosti.

67
00:03:41,870 --> 00:03:46,180
Pa evo, mi smo prolazu
izmijenjena vrijednosti polja.

68
00:03:46,180 --> 00:03:50,930
Ovaj vrijednosti plus srednje plus 1 je
zapravo govori rekurzivno poziva

69
00:03:50,930 --> 00:03:56,460
pretraživanje, prolazi u novom ruhu, gdje
da je novi niz počinje u sredini

70
00:03:56,460 --> 00:03:59,370
plus jedan je od naše izvorne vrijednosti niza.

71
00:03:59,370 --> 00:04:05,400
>> Alternativna sintaksa za to, sad kad
vi ste počeli vidjeti naputke, je

72
00:04:05,400 --> 00:04:10,170
Ampersand vrijednosti srednje plus 1.

73
00:04:10,170 --> 00:04:17,149
Dakle, zgrabite adresu sredini
plus jedan element vrijednosti.

74
00:04:17,149 --> 00:04:23,690
>> Sada, ako nije bilo ugodno
modificiranje niz kao što je to, što

75
00:04:23,690 --> 00:04:28,900
također mogao provesti to pomoću
rekurzivna funkcija pomagač, gdje

76
00:04:28,900 --> 00:04:31,680
da pomagač funkcije traje
više argumenata.

77
00:04:31,680 --> 00:04:36,610
Dakle, umjesto da samo vrijednost,
polje, a veličina polja,

78
00:04:36,610 --> 00:04:42,315
pomagač funkciju mogao uzeti više
argumenata, uključujući i donji indeksa

79
00:04:42,315 --> 00:04:45,280
da bi stalo u nizu
i gornji indeks da ti je stalo

80
00:04:45,280 --> 00:04:46,300
o nizu.

81
00:04:46,300 --> 00:04:49,770
>> I tako praćenje i manja
index i gornji indeks, ne znaš

82
00:04:49,770 --> 00:04:52,780
morati sve mijenjati
izvorne vrijednosti polja.

83
00:04:52,780 --> 00:04:56,390
Možete samo nastaviti
koristiti niz vrijednosti.

84
00:04:56,390 --> 00:04:59,540
Ali ovdje, primijetit ne trebamo pomagač
funkcionirati dokle god smo

85
00:04:59,540 --> 00:05:01,760
spremni mijenjati original
Vrijednosti polja.

86
00:05:01,760 --> 00:05:05,020
Mi smo spremni da prođe u
Ažurirani vrijednosti.

87
00:05:05,020 --> 00:05:09,140
>> Sada, ne možemo binarni pretragu
Niz je to nerazvrstani.

88
00:05:09,140 --> 00:05:12,220
Dakle, neka je dobiti ovaj izdvojiti.

89
00:05:12,220 --> 00:05:17,650
Sada, primijetiti da je sorta je posljednje dvije
Parametri int vrijednosti, što je

90
00:05:17,650 --> 00:05:21,110
Niz da sređujemo, a int n,
što je duljina niza koji

91
00:05:21,110 --> 00:05:22,250
sređujemo.

92
00:05:22,250 --> 00:05:24,840
Dakle, ovdje želimo provesti
sortiranje algoritam

93
00:05:24,840 --> 00:05:26,690
da je o n na kvadrat.

94
00:05:26,690 --> 00:05:30,560
Možete odabrati bubble sortiranje, odabir
sortiranje ili umetanje vrsta, ili

95
00:05:30,560 --> 00:05:32,670
neka druga vrsta nemamo
Vidio je u klasi.

96
00:05:32,670 --> 00:05:36,380
Ali ovdje, idemo u
Koristi odabir vrsta.

97
00:05:36,380 --> 00:05:40,030
>> Dakle, mi ćemo ponoviti
tijekom cijelog niza.

98
00:05:40,030 --> 00:05:44,360
Pa, ovdje vidimo da smo iterating
od 0 do N minus 1.

99
00:05:44,360 --> 00:05:45,990
Zašto ne skroz do n?

100
00:05:45,990 --> 00:05:49,320
Pa, ako smo već razvrstani prvi
n minus 1 elementi, zatim

101
00:05:49,320 --> 00:05:54,420
posljednji element koji ono mora biti već
na pravo mjesto, tako da tijekom sortiranja

102
00:05:54,420 --> 00:05:56,520
Cijeli niz.

103
00:05:56,520 --> 00:05:58,770
>> Sad, sjetite se kako je izbor
vrsta radova.

104
00:05:58,770 --> 00:06:01,950
Mi ćemo ići preko cijelog niza
u potrazi za minimalne vrijednosti u

105
00:06:01,950 --> 00:06:04,480
polje i stick koji
na početku.

106
00:06:04,480 --> 00:06:07,610
Onda ćemo ići preko cijelog
Niz opet u potrazi za sekundu

107
00:06:07,610 --> 00:06:10,410
najmanji element, a stick koji
u drugom položaju u

108
00:06:10,410 --> 00:06:12,100
polje, i tako dalje.

109
00:06:12,100 --> 00:06:14,330
Dakle, to je ono što ovaj radi.

110
00:06:14,330 --> 00:06:17,290
>> Evo, mi smo vidjeli da smo
postavljanje trenutni minimum

111
00:06:17,290 --> 00:06:20,030
vrijednost i-tog indeksa.

112
00:06:20,030 --> 00:06:23,160
Dakle, na prvoj iteraciji, idemo
uzeti u obzir minimalna vrijednost biti

113
00:06:23,160 --> 00:06:25,030
Početak našeg niza.

114
00:06:25,030 --> 00:06:28,500
Zatim ćemo ponoviti tijekom
Preostali dio polja, provjeravajući

115
00:06:28,500 --> 00:06:31,870
vidi ima li kakvih elemenata manji od
onaj koji smo trenutno

116
00:06:31,870 --> 00:06:33,900
s obzirom na minimum.

117
00:06:33,900 --> 00:06:38,840
>> Pa evo, vrijednosti j plus jedan - to je
manje od onoga što smo mi sada

118
00:06:38,840 --> 00:06:40,380
s obzirom na minimum.

119
00:06:40,380 --> 00:06:42,940
Onda ćemo ažurirati što
mi mislimo da je minimalno za

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

121
00:06:44,640 --> 00:06:48,540
Dakle, to učiniti preko cijelog niza,
, a nakon toga za petlje, minimum

122
00:06:48,540 --> 00:06:53,160
trebao biti minimalan element iz
i-ti položaj u nizu.

123
00:06:53,160 --> 00:06:57,350
>> Nakon što smo to, možemo mijenjati
Minimalna vrijednost u i-tom položaju

124
00:06:57,350 --> 00:06:58,230
u polju.

125
00:06:58,230 --> 00:07:00,130
Dakle, ovo je samo standardni swapa.

126
00:07:00,130 --> 00:07:03,940
Mi pohraniti u privremenu vrijednosti -
i-vrijednost u polju -

127
00:07:03,940 --> 00:07:08,460
staviti u i-tom vrijednosti u polju
Minimalna vrijednost koja pripada tamo,

128
00:07:08,460 --> 00:07:13,580
a potom pohraniti natrag u kojoj
Trenutna minimalna vrijednost koja se koristi kako bi se

129
00:07:13,580 --> 00:07:16,460
i-vrijednost u polju, pa
da nismo izgubili.

130
00:07:16,460 --> 00:07:20,510
>> Dakle, da se nastavlja
Sljedeća iteracija.

131
00:07:20,510 --> 00:07:23,480
Mi ćemo početi tražiti drugi
Minimalna vrijednost i umetnite ga u

132
00:07:23,480 --> 00:07:24,590
drugo mjesto.

133
00:07:24,590 --> 00:07:27,440
Na trećoj iteraciji, mi ćemo tražiti
Treći minimalna vrijednost i umetak

134
00:07:27,440 --> 00:07:31,550
da u treći položaj, i tako
sve dok imamo sortirani niz.

135
00:07:31,550 --> 00:07:33,820
Moje ime je Rob, a to
bio izbor vrsta.

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