1
00:00:00,000 --> 00:00:08,532
>> [Música tocando]

2
00:00:08,532 --> 00:00:12,060
>> ZAMYLA CHAN: A primeira cousa que pode
aviso sobre descubrimento é que xa

3
00:00:12,060 --> 00:00:13,450
ter o código escrito para nós.

4
00:00:13,450 --> 00:00:15,160
Isto chámase código de distribución.

5
00:00:15,160 --> 00:00:18,000
Polo tanto, non estamos só escribindo o noso propio
código de cero máis.

6
00:00:18,000 --> 00:00:22,800
Pola contra, estamos cubrindo os baleiros
nalgún código pre-existente.

7
00:00:22,800 --> 00:00:27,790
>> O programa find.c solicita números
para cubrir o palheiro, busca o

8
00:00:27,790 --> 00:00:32,189
chea de feno para unha agulla usuario enviou,
e el fai iso chamando clasificar e

9
00:00:32,189 --> 00:00:35,590
busca, funcións definidas
en helpers.c.

10
00:00:35,590 --> 00:00:37,670
Así find.c está escrita xa.

11
00:00:37,670 --> 00:00:40,770
O seu traballo é escribir axudantes.

12
00:00:40,770 --> 00:00:41,870
>> Entón, o que estamos facendo?

13
00:00:41,870 --> 00:00:44,210
Estamos aplicando dúas funcións.

14
00:00:44,210 --> 00:00:49,030
Investigación, que retorna true se un valor
se atopa en palheiro, retornando

15
00:00:49,030 --> 00:00:51,370
false se o valor é
non no palheiro.

16
00:00:51,370 --> 00:00:57,990
E entón nós tamén estamos aplicando tipo
que clasifica o array chamado valores.

17
00:00:57,990 --> 00:00:59,960
>> Entón, imos afrontar investigación.

18
00:00:59,960 --> 00:01:04,560
Busca é aplicado actualmente como un
busca lineal, pero pode facer moito

19
00:01:04,560 --> 00:01:05,550
mellor que iso.

20
00:01:05,550 --> 00:01:09,910
Busca linear é aplicada no
de tempo n, o que é moi lento.

21
00:01:09,910 --> 00:01:13,850
Aínda que, pode buscar
calquera lista que lle é dado.

22
00:01:13,850 --> 00:01:20,130
O seu traballo é a implementación de busca binaria,
que ten tempo de execución O de rexistro n.

23
00:01:20,130 --> 00:01:21,130
Isto é moi rápido.

24
00:01:21,130 --> 00:01:23,170
>> Pero hai unha condición.

25
00:01:23,170 --> 00:01:27,600
Busca binaria só pode buscar
mediante listas pre-ordenada.

26
00:01:27,600 --> 00:01:30,370
Por que isto?

27
00:01:30,370 --> 00:01:32,620
>> Ben, imos ollar un exemplo.

28
00:01:32,620 --> 00:01:36,280
Dada unha matriz de valores, o palheiro,
imos estar a ollar

29
00:01:36,280 --> 00:01:37,130
para unha agulla.

30
00:01:37,130 --> 00:01:40,460
E, neste exemplo,
o número enteiro tres.

31
00:01:40,460 --> 00:01:44,130
O xeito que busca binaria funciona é que
compararmos o valor medio de

32
00:01:44,130 --> 00:01:48,370
a matriz para a agulla, así como o xeito no que
abrimos unha axenda para o medio

33
00:01:48,370 --> 00:01:50,660
Páxina a semana cero.

34
00:01:50,660 --> 00:01:54,650
>> Entón, despois de comparar o valor medio para
a agulla, pode descartar ou a

35
00:01:54,650 --> 00:01:58,530
esquerda ou da metade dereita da matriz
axustado os seus límites.

36
00:01:58,530 --> 00:02:03,390
Neste caso, xa que tres, a agulla,
é inferior a 10, o valor medio, o

37
00:02:03,390 --> 00:02:05,990
certo límite pode diminuír.

38
00:02:05,990 --> 00:02:08,400
Pero probe facer os seus límites
tan axustado como sexa posible.

39
00:02:08,400 --> 00:02:11,630
O valor do medio non é a agulla,
entón vostede sabe que non é preciso

40
00:02:11,630 --> 00:02:13,010
inclui-lo na súa procura.

41
00:02:13,010 --> 00:02:17,310
Entón está certo límite pode usar a
límites da investigación só un pouquiño máis,

42
00:02:17,310 --> 00:02:21,770
e así por diante e así por diante ata
atopa a súa agulla.

43
00:02:21,770 --> 00:02:23,480
>> Entón, o que o pseudocódigo parece?

44
00:02:23,480 --> 00:02:28,420
Así, mentres que nós aínda estamos mirando a través
da lista e aínda ten elementos para

45
00:02:28,420 --> 00:02:33,690
ollar nos, tomamos a través da lista,
e comparar o valor medio para

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

47
00:02:34,950 --> 00:02:37,310
Se son iguais, entón iso significa que temos
atopou a agulla e podemos

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

49
00:02:38,990 --> 00:02:42,870
>> En caso contrario, se a agulla é inferior a
o valor medio, a continuación, isto significa que

50
00:02:42,870 --> 00:02:47,280
pode descartar a metade dereita, e só
buscar o lado esquerdo da matriz.

51
00:02:47,280 --> 00:02:51,090
En caso contrario, nós imos buscar o
lado dereito da matriz.

52
00:02:51,090 --> 00:02:54,410
E, ao final, se non ten ningún
máis elementos de esquerda a procura, pero

53
00:02:54,410 --> 00:02:58,050
non atopou a súa agulla aínda, entón
return false porque a agulla

54
00:02:58,050 --> 00:03:01,890
En definitiva, non é no palheiro.

55
00:03:01,890 --> 00:03:05,270
>> Agora, unha cousa interesante sobre este pseudocódigo
en busca binaria é que pode ser

56
00:03:05,270 --> 00:03:09,940
interpretado como un iterativo
ou implantación recursiva.

57
00:03:09,940 --> 00:03:13,810
Polo tanto, sería recursiva se chama
a función de investigación dentro da investigación

58
00:03:13,810 --> 00:03:17,350
funciona en calquera das metades da matriz.

59
00:03:17,350 --> 00:03:21,030
Nós imos cubrir recursão un pouco máis tarde no
claro, pero sei que el é un

60
00:03:21,030 --> 00:03:24,190
opción se quere probar.

61
00:03:24,190 --> 00:03:26,030
>> Agora imos ollar para o tipo.

62
00:03:26,030 --> 00:03:30,750
Ordenar recibe un array eo enteiro
n, que é o tamaño da matriz.

63
00:03:30,750 --> 00:03:34,030
Agora, hai varios tipos diferentes
das sortes, e pode ollar para algúns

64
00:03:34,030 --> 00:03:36,370
shorts para demostracións e explicacións.

65
00:03:36,370 --> 00:03:39,580
O tipo de retorno para o noso
función de clasificación é nula.

66
00:03:39,580 --> 00:03:43,580
Entón iso significa que nós non imos
para voltar calquera matriz de tipo.

67
00:03:43,580 --> 00:03:48,140
En realidade, estamos indo a cambiar a propia
matriz que foi pasado para nós.

68
00:03:48,140 --> 00:03:52,290
>> E isto é posible porque as matrices son
pasados ​​por referencia en C. Agora imos

69
00:03:52,290 --> 00:03:55,290
ver máis sobre iso máis tarde, pero o
diferenza esencial entre pasaxe

70
00:03:55,290 --> 00:03:59,340
en algo así como un enteiro e paso
nunha matriz, é que cando

71
00:03:59,340 --> 00:04:03,490
pasar nun enteiro, C só vai
facer unha copia deste enteiro e pasar

72
00:04:03,490 --> 00:04:04,450
lo para a función.

73
00:04:04,450 --> 00:04:08,530
A variable orixinal non será modificado
xa que a función é rematada.

74
00:04:08,530 --> 00:04:12,480
Cunha disposición, por outra banda, é
Non vai facer unha copia, e vai

75
00:04:12,480 --> 00:04:17,910
en realidade, ser de editar o
si moi array.

76
00:04:17,910 --> 00:04:21,269
>> Así, un tipo de especie é
o tipo de selección.

77
00:04:21,269 --> 00:04:24,750
O tipo de selección funciona desde
o principio, e entón iterado

78
00:04:24,750 --> 00:04:26,820
máis e atopar o menor elemento.

79
00:04:26,820 --> 00:04:30,710
E entón intercambiar que a menor
elemento co primeiro.

80
00:04:30,710 --> 00:04:34,360
E entón se move para o segundo elemento
, O seguinte menor

81
00:04:34,360 --> 00:04:38,320
elemento, e cambiar iso co
segundo elemento na matriz, xa

82
00:04:38,320 --> 00:04:41,100
o primeiro elemento xa está clasificada.

83
00:04:41,100 --> 00:04:45,370
E entón segue para cada
elemento de identificación do menor

84
00:04:45,370 --> 00:04:47,690
valor e intercambio-lo para fóra.

85
00:04:47,690 --> 00:04:53,460
>> Pois é igual a 0, o primeiro elemento
para n menos 1, está indo a comparar

86
00:04:53,460 --> 00:04:57,820
cada valor seguinte e logo que atopar
o índice do valor mínimo.

87
00:04:57,820 --> 00:05:02,520
Despois de atopar o índice de valor mínimo,
pode cambiar o valor dun array

88
00:05:02,520 --> 00:05:05,930
I. mínimo e disposición

89
00:05:05,930 --> 00:05:09,760
>> Outro tipo de clasificación que se pode
aplicar é bubble sort.

90
00:05:09,760 --> 00:05:14,380
Entón repite Bubble Sort sobre a lista
comparar os elementos adxacentes e

91
00:05:14,380 --> 00:05:17,720
cambiando os elementos que
están na orde errada.

92
00:05:17,720 --> 00:05:22,380
E deste xeito, o maior elemento
vai borbulhar ata o final.

93
00:05:22,380 --> 00:05:28,070
E a lista é ordenada unha vez máis
elementos foron trocados.

94
00:05:28,070 --> 00:05:31,920
>> Entón eses son dous exemplos de tipo
algoritmos que pode aplicar para

95
00:05:31,920 --> 00:05:33,230
o programa de descubrimento.

96
00:05:33,230 --> 00:05:37,350
Unha vez que termine de clasificación, e ten
feito de procura, está acabado.

97
00:05:37,350 --> 00:05:39,720
O meu nome é Zamyla, e este é CS50.

98
00:05:39,720 --> 00:05:46,987
>> [Música tocando]