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

2
00:00:13,300 --> 00:00:15,010
>> ROB Bowden: Hola, sóc Rob.

3
00:00:15,010 --> 00:00:16,790
Com ens emprem una recerca binària?

4
00:00:16,790 --> 00:00:18,770
Anem a veure.

5
00:00:18,770 --> 00:00:23,400
Per tant, tingueu en compte que aquesta recerca ens anem
per aplicar de forma recursiva.

6
00:00:23,400 --> 00:00:27,470
Vostè podria també posar en pràctica la recerca binària
iterativa, pel que si es va fer,

7
00:00:27,470 --> 00:00:29,280
que està perfectament bé.

8
00:00:29,280 --> 00:00:32,820
>> Ara primer, recordem el que el
paràmetres de cerca estan destinats a ser.

9
00:00:32,820 --> 00:00:36,120
Aquí, veiem valor int, que és
suposa que és el valor que l'usuari és

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

11
00:00:37,320 --> 00:00:40,800
Veiem la matriu valors int, que
és la matriu en la qual estem

12
00:00:40,800 --> 00:00:42,520
la recerca de valor.

13
00:00:42,520 --> 00:00:45,602
I veiem int n, que és
la durada de la nostra matriu.

14
00:00:45,602 --> 00:00:47,410
>> Ara, primer el primer.

15
00:00:47,410 --> 00:00:51,350
Verifiquem si n és igual a 0, en
aquest cas tornem falsa.

16
00:00:51,350 --> 00:00:54,770
Això és només dir si tenim un buit
matriu, el valor no és clara en un

17
00:00:54,770 --> 00:00:57,860
matriu buida, pel que pot tornar false.

18
00:00:57,860 --> 00:01:01,250
>> Ara, en realitat volem fer el binari
Cerca part de recerca binària.

19
00:01:01,250 --> 00:01:04,780
Per tant, volem trobar el mitjà
element d'aquesta matriu.

20
00:01:04,780 --> 00:01:09,130
Aquí, diem mitjana és igual a n dividida
per 2, ja que l'element mitjà és

21
00:01:09,130 --> 00:01:12,240
serà la longitud d'
nostra matriu dividida per 2.

22
00:01:12,240 --> 00:01:15,040
Ara anem a comprovar per veure si el
element mitjà és igual al valor que estem

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

24
00:01:16,160 --> 00:01:21,030
Així que si els valors de mitjana és igual a valor,
pot retornar cert ja que trobem el

25
00:01:21,030 --> 00:01:22,810
valor a la nostra matriu.

26
00:01:22,810 --> 00:01:26,380
>> Però si això no era cert, ara
hem de fer el recursiva

27
00:01:26,380 --> 00:01:27,840
pas de cerca binària.

28
00:01:27,840 --> 00:01:30,450
Hem de buscar o bé a la
esquerra de la matriu o de la

29
00:01:30,450 --> 00:01:32,320
centre de la matriu.

30
00:01:32,320 --> 00:01:39,280
Així que aquí, diem si els valors en el medi és
menys del seu valor, això significa que el valor

31
00:01:39,280 --> 00:01:41,350
va ser major que la meitat
de la matriu.

32
00:01:41,350 --> 00:01:45,790
Així que el valor ha de ser el de la dreta de la
element que acabem de veure.

33
00:01:45,790 --> 00:01:48,090
>> Així que aquí, anem a
buscar de forma recursiva.

34
00:01:48,090 --> 00:01:50,320
I anem a veure el que estem passant
a aquest en un segon.

35
00:01:50,320 --> 00:01:53,440
Però anem a buscar la
dreta de l'element mitjà.

36
00:01:53,440 --> 00:01:57,710
I en l'altre cas, el que significa que
valor va ser de menys de la meitat de la

37
00:01:57,710 --> 00:02:00,660
matriu, i així anem
per buscar a l'esquerra.

38
00:02:00,660 --> 00:02:03,520
Ara, l'esquerra serà
una mica més fàcil de veure.

39
00:02:03,520 --> 00:02:07,770
Així, veiem aquí que estem recursiva
trucant recerca on la primera

40
00:02:07,770 --> 00:02:10,120
argument és, de nou, el valor
estem mirant per sobre.

41
00:02:10,120 --> 00:02:14,970
El segon argument serà el
matriu que buscàvem acabat.

42
00:02:14,970 --> 00:02:17,090
I l'últim element actual és mitjà.

43
00:02:17,090 --> 00:02:21,650
Recordeu que l'últim paràmetre és la nostra int
n, de manera que aquesta és la durada de la nostra matriu.

44
00:02:21,650 --> 00:02:25,310
>> A la crida recursiva a buscar, estem
ara dient que la longitud de la

45
00:02:25,310 --> 00:02:27,230
array és mitjà.

46
00:02:27,230 --> 00:02:32,900
Per tant, si la nostra matriu era de mida 20 i
buscat en l'índex 10, ja que al mig és

47
00:02:32,900 --> 00:02:36,930
20 dividit entre 2, això significa que estem
passar 10 com la nova

48
00:02:36,930 --> 00:02:38,300
longitud de la nostra matriu.

49
00:02:38,300 --> 00:02:41,910
Recordeu que quan vostè té una matriu
de longitud 10, això significa que la validesa

50
00:02:41,910 --> 00:02:45,450
els elements estan en els índexs de 0 a 9.

51
00:02:45,450 --> 00:02:50,120
Així que això és exactament el que volem
especificar la nostra gamma actualitzada - l'esquerra

52
00:02:50,120 --> 00:02:53,010
matriu des de l'element mitjà.

53
00:02:53,010 --> 00:02:55,710
>> Així que, mirant cap a la dreta és
una mica més difícil.

54
00:02:55,710 --> 00:03:00,170
Ara en primer lloc, anem a considerar la longitud
de la matriu a la dreta de la

55
00:03:00,170 --> 00:03:01,240
element mitjà.

56
00:03:01,240 --> 00:03:08,390
Per tant, si la nostra matriu era de grandària n, llavors el
nova matriu serà de grandària n menys

57
00:03:08,390 --> 00:03:10,140
almenys la meitat gener.

58
00:03:10,140 --> 00:03:12,530
Per tant, anem a pensar en n menys mig.

59
00:03:12,530 --> 00:03:18,710
>> Un cop més, si la matriu van ser de mida 20 i
dividim per 2 per obtenir el mitjà,

60
00:03:18,710 --> 00:03:23,540
de manera que el mitjà és 10, llavors n almenys mig
ens donarà el 10, així que 10

61
00:03:23,540 --> 00:03:25,330
elements a la dreta del centre.

62
00:03:25,330 --> 00:03:27,780
Però també tenim la menys
1, ja que no volem

63
00:03:27,780 --> 00:03:29,700
incloure el propi medi.

64
00:03:29,700 --> 00:03:34,190
Llavors n almenys mitja menys 1 ens dóna la
nombre total d'elements a la dreta

65
00:03:34,190 --> 00:03:36,800
l'índex mitjà de la matriu.

66
00:03:36,800 --> 00:03:41,870
>> Ara aquí, recordar que el medi
paràmetre és la matriu de valors.

67
00:03:41,870 --> 00:03:46,180
Així que aquí, estem passant una
actualitzat array valors.

68
00:03:46,180 --> 00:03:50,930
Això a més dels valors, més mitjà 1 és
dient realment recursiva anomenada

69
00:03:50,930 --> 00:03:56,460
recerca, passant per una nova matriu, on
que la nova matriu comença en el medi

70
00:03:56,460 --> 00:03:59,370
més un de la nostra sèrie els valors originals.

71
00:03:59,370 --> 00:04:05,400
>> Una sintaxi alternativa perquè, ara que
que ha començat a veure els punters, és

72
00:04:05,400 --> 00:04:10,170
valors ampersand més mitjana 1.

73
00:04:10,170 --> 00:04:17,149
Així, pren la direcció del centre
a més d'un element dels valors.

74
00:04:17,149 --> 00:04:23,690
>> Ara, si vostè no estava còmode
modificació d'una sèrie com aquesta,

75
00:04:23,690 --> 00:04:28,900
També podria haver implementat aquesta usant
una funció auxiliar recursiva, on

76
00:04:28,900 --> 00:04:31,680
funció auxiliar que pren
més arguments.

77
00:04:31,680 --> 00:04:36,610
Així que en lloc de prendre només el valor,
matriu, i la mida de la matriu,

78
00:04:36,610 --> 00:04:42,315
la funció auxiliar podria prendre més
arguments, inclosos l'índex més baix

79
00:04:42,315 --> 00:04:45,280
que a vostè li preocupen a la matriu
i l'índex superior que es preocupa

80
00:04:45,280 --> 00:04:46,300
sobre la matriu.

81
00:04:46,300 --> 00:04:49,770
>> I així no perdre de vista tant de la menor
índex i l'índex superior, que no ho fan

82
00:04:49,770 --> 00:04:52,780
s'hagi de modificar mai la
valors originals matriu.

83
00:04:52,780 --> 00:04:56,390
Vostè només pot seguir
utilitzar la matriu de valors.

84
00:04:56,390 --> 00:04:59,540
Però aquí, notem que no necessitem un ajudant
funcionar, sempre que estiguem

85
00:04:59,540 --> 00:05:01,760
disposats per modificar l'original
valors d'array.

86
00:05:01,760 --> 00:05:05,020
Estem disposats a passar
01:00 valors actualitzats.

87
00:05:05,020 --> 00:05:09,140
>> Ara, no podem recerca binària sobre
una matriu que és classificar.

88
00:05:09,140 --> 00:05:12,220
Així que anem a obtenir aquesta resolt.

89
00:05:12,220 --> 00:05:17,650
Ara, observi que tipus és les dues i
paràmetres int valors, que és el

90
00:05:17,650 --> 00:05:21,110
matriu que estem ordenar i int n,
que és la longitud de la matriu que

91
00:05:21,110 --> 00:05:22,250
estem ordenació.

92
00:05:22,250 --> 00:05:24,840
Així doncs, aquí volem implementar
un algorisme d'ordenació

93
00:05:24,840 --> 00:05:26,690
és a dir o de n al quadrat.

94
00:05:26,690 --> 00:05:30,560
Vostè pot optar per l'ordenació de bombolla, la selecció
tipus, o l'ordenació per inserció, o

95
00:05:30,560 --> 00:05:32,670
algun altre tipus que no tenim
vist a classe.

96
00:05:32,670 --> 00:05:36,380
Però aquí, anem a
utilitzar la selecció de gènere.

97
00:05:36,380 --> 00:05:40,030
>> Per tant, repetirem
sobre tota la matriu.

98
00:05:40,030 --> 00:05:44,360
Bé, aquí veiem que estem iterant
de 0 a n almenys 1.

99
00:05:44,360 --> 00:05:45,990
Per què no tot el camí fins al n?

100
00:05:45,990 --> 00:05:49,320
Bé, si ja hem va solucionar la primera
N almenys 1 elements, llavors el

101
00:05:49,320 --> 00:05:54,420
últim element del que ja ha de ser
en el lloc correcte, de manera que la classificació més

102
00:05:54,420 --> 00:05:56,520
tota la matriu.

103
00:05:56,520 --> 00:05:58,770
>> Ara, recorda com la selecció
tipus d'obres.

104
00:05:58,770 --> 00:06:01,950
Anem a repassar tota la matriu
buscant el valor mínim

105
00:06:01,950 --> 00:06:04,480
la matriu i el pal que
al principi.

106
00:06:04,480 --> 00:06:07,610
A continuació repassarem tota la
array de nou a la recerca de la segona

107
00:06:07,610 --> 00:06:10,410
element més petit, i el pal que
en la segona posició en el

108
00:06:10,410 --> 00:06:12,100
matriu, i així successivament.

109
00:06:12,100 --> 00:06:14,330
Llavors, això és el que està fent.

110
00:06:14,330 --> 00:06:17,290
>> Aquí, estem veient que estem
establint el mínim actual

111
00:06:17,290 --> 00:06:20,030
valor per a l'índex i.

112
00:06:20,030 --> 00:06:23,160
Així que en la primera iteració, anem
considerar el valor mínim per ser

113
00:06:23,160 --> 00:06:25,030
el començament de la nostra matriu.

114
00:06:25,030 --> 00:06:28,500
Llavors, repetirem l'
resta de la gamma, verificant

115
00:06:28,500 --> 00:06:31,870
veure si hi ha algun element més petit que
la qual estem actualment

116
00:06:31,870 --> 00:06:33,900
tenint en compte el mínim.

117
00:06:33,900 --> 00:06:38,840
>> Així que aquí, els valors j més un - que és
menys del que som en l'actualitat

118
00:06:38,840 --> 00:06:40,380
tenint en compte el mínim.

119
00:06:40,380 --> 00:06:42,940
Llavors anem a actualitzar el
que creiem que és el mínim per

120
00:06:42,940 --> 00:06:44,640
índex j més 1.

121
00:06:44,640 --> 00:06:48,540
Per tant, fer que a través de tota la matriu,
i després d'aquest bucle, mínim

122
00:06:48,540 --> 00:06:53,160
ha de ser l'element mínim de
la posició i-èsima de la matriu.

123
00:06:53,160 --> 00:06:57,350
>> Un cop tinguem això, podem intercanviar la
valor mínim en la posició i-èsima

124
00:06:57,350 --> 00:06:58,230
en la matriu.

125
00:06:58,230 --> 00:07:00,130
Així que això és només un intercanvi estàndard.

126
00:07:00,130 --> 00:07:03,940
Nosaltres guardem en un valor temporal -
el valor i-èsim de la matriu -

127
00:07:03,940 --> 00:07:08,460
posat en el valor i-èsim de la matriu de la
valor mínim que pertany allà,

128
00:07:08,460 --> 00:07:13,580
i després emmagatzemar de nou on el
valor mínim actual que solia ser el

129
00:07:13,580 --> 00:07:16,460
i-èsim valor de la matriu, de manera que
que no ens perdem.

130
00:07:16,460 --> 00:07:20,510
>> Així, que continua en
la següent iteració.

131
00:07:20,510 --> 00:07:23,480
Anem a començar a buscar el segon
valor mínim i que publicarà al

132
00:07:23,480 --> 00:07:24,590
segona posició.

133
00:07:24,590 --> 00:07:27,440
A la tercera iteració, buscarem
el tercer valor mínim i l'insert

134
00:07:27,440 --> 00:07:31,550
que en la tercera posició, i així
fins que tenim una matriu ordenada.

135
00:07:31,550 --> 00:07:33,820
El meu nom és Rob, i això
era una mena de selecció.

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