1
00:00:00,000 --> 00:00:08,532
>> [REPRODUCCIÓ DE MÚSICA]

2
00:00:08,532 --> 00:00:12,060
>> ZAMYLA CHAN: La primera cosa que vostè podria
avís sobre troballa és que ja

3
00:00:12,060 --> 00:00:13,450
haver codi escrit per a nosaltres.

4
00:00:13,450 --> 00:00:15,160
Això es diu codi de distribució.

5
00:00:15,160 --> 00:00:18,000
Així que no només estem escrivint la nostra pròpia
codi des de zero ja.

6
00:00:18,000 --> 00:00:22,800
Més aviat, estem omplint els buits
en algun codi preexistent.

7
00:00:22,800 --> 00:00:27,790
>> El programa find.c sol · licita números
per omplir el paller, cerca la

8
00:00:27,790 --> 00:00:32,189
Haystack per una agulla enviat pels usuaris,
i ho fa cridant a classificar i

9
00:00:32,189 --> 00:00:35,590
de recerca, funcions definides
en helpers.c.

10
00:00:35,590 --> 00:00:37,670
Així find.c està ja escrit.

11
00:00:37,670 --> 00:00:40,770
El seu treball és escriure ajudants.

12
00:00:40,770 --> 00:00:41,870
>> Llavors, què estem fent?

13
00:00:41,870 --> 00:00:44,210
Estem implementant dues funcions.

14
00:00:44,210 --> 00:00:49,030
Cerca, que retorna true si un valor
es troba al paller, tornant

15
00:00:49,030 --> 00:00:51,370
false si el valor és
no en el paller.

16
00:00:51,370 --> 00:00:57,990
I llavors nosaltres també estem implementant espècie
que ordena la matriu anomenada valors.

17
00:00:57,990 --> 00:00:59,960
>> Així que anem a abordar en aquesta categoria.

18
00:00:59,960 --> 00:01:04,560
Cercar Actualment s'implementa com un
recerca lineal, però es pot fer molt

19
00:01:04,560 --> 00:01:05,550
millor que això.

20
00:01:05,550 --> 00:01:09,910
Hi lineal s'implementa a O
de temps n, que és bastant lent.

21
00:01:09,910 --> 00:01:13,850
Encara que, pot buscar
qualsevol llista que se li dóna.

22
00:01:13,850 --> 00:01:20,130
El seu treball consisteix a posar en pràctica la recerca binària,
que s'ha quedat temps O de registre núm.

23
00:01:20,130 --> 00:01:21,130
Això és bastant ràpid.

24
00:01:21,130 --> 00:01:23,170
>> Però hi ha una condició.

25
00:01:23,170 --> 00:01:27,600
Cerca binària només pot buscar
a través de les llistes de pre-ordenats.

26
00:01:27,600 --> 00:01:30,370
Per què?

27
00:01:30,370 --> 00:01:32,620
>> Bé anem a veure un exemple.

28
00:01:32,620 --> 00:01:36,280
Donada una matriu de valors, el paller,
estarem buscant

29
00:01:36,280 --> 00:01:37,130
per una agulla.

30
00:01:37,130 --> 00:01:40,460
I en aquest exemple,
el nombre enter 3.

31
00:01:40,460 --> 00:01:44,130
La forma en què la recerca binària funciona és que
es compara el valor mitjà de

32
00:01:44,130 --> 00:01:48,370
la matriu a l'agulla, igual que la manera
obrim una agenda per al medi

33
00:01:48,370 --> 00:01:50,660
pàgina en la setmana zero.

34
00:01:50,660 --> 00:01:54,650
>> Així que després de comparar el valor mitjà de
l'agulla, es pot descartar tampoc la

35
00:01:54,650 --> 00:01:58,530
esquerra o la meitat dreta de la matriu
estrenyent els seus límits.

36
00:01:58,530 --> 00:02:03,390
En aquest cas, ja que tres, la nostra agulla,
és menys de 10, el valor mitjà, la

37
00:02:03,390 --> 00:02:05,990
dret d'Unió es reduirà.

38
00:02:05,990 --> 00:02:08,400
Però tractar de fer que els seus límits
el més ajustat possible.

39
00:02:08,400 --> 00:02:11,630
Si el valor mitjà no és l'agulla,
llavors vostè sap que vostè no ha de

40
00:02:11,630 --> 00:02:13,010
incloure en la seva recerca.

41
00:02:13,010 --> 00:02:17,310
Així que estàs en el cert límit pot prémer la
recerca surt una miqueta més,

42
00:02:17,310 --> 00:02:21,770
i així successivament i així successivament fins
a trobar el seu agulla.

43
00:02:21,770 --> 00:02:23,480
>> Llavors, què fa el pseudocodi sembla?

44
00:02:23,480 --> 00:02:28,420
Bé, mentre que encara estem mirant a través de
la llista i tot i així tenir elements per

45
00:02:28,420 --> 00:02:33,690
Cerca a, prenem la meitat de la llista,
i comparar aquest valor mitjà de

46
00:02:33,690 --> 00:02:34,950
nostra agulla.

47
00:02:34,950 --> 00:02:37,310
Si són iguals, llavors això vol dir que hem
trobat l'agulla i podem

48
00:02:37,310 --> 00:02:38,990
return true.

49
00:02:38,990 --> 00:02:42,870
>> En cas contrari, si l'agulla és menys de
el valor mitjà, llavors això vol dir que

50
00:02:42,870 --> 00:02:47,280
pot descartar la meitat dreta, i just
buscar el costat esquerre de la matriu.

51
00:02:47,280 --> 00:02:51,090
En cas contrari, anem a buscar la
costat dret de la matriu.

52
00:02:51,090 --> 00:02:54,410
I al final, si vostè no té cap
més elements que deixen de buscar, però que

53
00:02:54,410 --> 00:02:58,050
no ha trobat el seu agulla encara, llavors vostè
return false perquè l'agulla

54
00:02:58,050 --> 00:03:01,890
definitivament no es troba en el paller.

55
00:03:01,890 --> 00:03:05,270
>> Ara, una cosa polida sobre aquest pseudocodi
en recerca binària és que pot ser

56
00:03:05,270 --> 00:03:09,940
interpretar-se com un procés iteratiu
o implementació recursiva.

57
00:03:09,940 --> 00:03:13,810
Així que seria recursiu si es diu
la funció de cerca a la recerca

58
00:03:13,810 --> 00:03:17,350
funcionar en qualsevol de la meitat de la matriu.

59
00:03:17,350 --> 00:03:21,030
Anem a cobrir la recursivitat una mica més tard en el
per descomptat, però sí sabem que es tracta d'un

60
00:03:21,030 --> 00:03:24,190
opció si voleu provar.

61
00:03:24,190 --> 00:03:26,030
>> Ara donem una ullada a classe.

62
00:03:26,030 --> 00:03:30,750
Ordenar pren una matriu i el nombre sencer
n, que és la mida de la matriu.

63
00:03:30,750 --> 00:03:34,030
Ara bé, hi ha diversos tipus diferents
de les classes, i es pot veure en alguns

64
00:03:34,030 --> 00:03:36,370
pantalons curts per a demostracions i explicacions.

65
00:03:36,370 --> 00:03:39,580
El tipus de canvi de la nostra
funció de classificació és nul · la.

66
00:03:39,580 --> 00:03:43,580
Així que això significa que no anem
per retornar qualsevol matriu d'ordenació.

67
00:03:43,580 --> 00:03:48,140
Estem realment canviarà la mateixa
matriu que es va passar a nosaltres.

68
00:03:48,140 --> 00:03:52,290
>> I això és possible perquè les matrius són
passen per referència a C. Ara anem a

69
00:03:52,290 --> 00:03:55,290
veure més sobre això més endavant, però el
diferència essencial entre passar

70
00:03:55,290 --> 00:03:59,340
en una mena sencer i passa
en una matriu, és que quan es

71
00:03:59,340 --> 00:04:03,490
passar en un enter, C és només va a
fer una còpia d'aquest sencer i passar

72
00:04:03,490 --> 00:04:04,450
a la funció.

73
00:04:04,450 --> 00:04:08,530
No es modificarà la variable original
una vegada que la funció ha acabat.

74
00:04:08,530 --> 00:04:12,480
Amb una matriu, d'altra banda, és
no farà una còpia, i vostè

75
00:04:12,480 --> 00:04:17,910
en realitat ser l'edició de la
si molt array.

76
00:04:17,910 --> 00:04:21,269
>> Així que un tipus d'espècie és
el tipus de selecció.

77
00:04:21,269 --> 00:04:24,750
L'ordenació per selecció Funciona a partir de les
Al principi, i després iterar

78
00:04:24,750 --> 00:04:26,820
una vegada i trobar l'element més petit.

79
00:04:26,820 --> 00:04:30,710
I llavors canvies que els més petits
element amb la primera.

80
00:04:30,710 --> 00:04:34,360
I llavors vostè es mou al segon element
, Cerca la següent més petita

81
00:04:34,360 --> 00:04:38,320
element, i després d'intercanvi que amb la
segon element de la matriu, ja

82
00:04:38,320 --> 00:04:41,100
el primer element apareix ordenat.

83
00:04:41,100 --> 00:04:45,370
I llavors vostè continua per a cada
element en la identificació de la més petita

84
00:04:45,370 --> 00:04:47,690
valor i la barata d'una ullada.

85
00:04:47,690 --> 00:04:53,460
>> Per I és igual a 0, el primer element
a n menys 1, vas a comparar

86
00:04:53,460 --> 00:04:57,820
cada valor següent després d'això i trobar
l'índex del valor mínim.

87
00:04:57,820 --> 00:05:02,520
Quan trobi l'índex de valor mínim,
vostè pot canviar el valor de la matriu

88
00:05:02,520 --> 00:05:05,930
mínim i varietat I.

89
00:05:05,930 --> 00:05:09,760
>> Un altre tipus d'espècie que pugui
implementar és l'ordenació de bombolla.

90
00:05:09,760 --> 00:05:14,380
Així es repeteix bombolla ordenar més de la llista
la comparació dels elements adjacents i

91
00:05:14,380 --> 00:05:17,720
l'intercanvi dels elements que
estan en l'ordre equivocat.

92
00:05:17,720 --> 00:05:22,380
I d'aquesta manera, l'element més gran
burbujeará fins al final.

93
00:05:22,380 --> 00:05:28,070
I la llista s'ordena una vegada més
elements s'han intercanviat.

94
00:05:28,070 --> 00:05:31,920
>> Així que aquests són dos exemples d'una espècie
algoritmes que es poden implementar per

95
00:05:31,920 --> 00:05:33,230
el programa de recerca.

96
00:05:33,230 --> 00:05:37,350
Quan acabi d'ordenar i tens
Cerca fet, hagi acabat.

97
00:05:37,350 --> 00:05:39,720
El meu nom és Zamyla, i això és CS50.

98
00:05:39,720 --> 00:05:46,987
>> [REPRODUCCIÓ DE MÚSICA]