1
00:00:00,000 --> 00:00:09,560

2
00:00:09,560 --> 00:00:13,120
>> ZAMYLA CHAN: A primeira cousa que pode
aviso sobre descubrimento é que xa

3
00:00:13,120 --> 00:00:14,520
ter o código escrito para nós.

4
00:00:14,520 --> 00:00:16,219
Isto chámase código de distribución.

5
00:00:16,219 --> 00:00:19,060
Polo tanto, non estamos só escribindo o noso propio
código de cero máis.

6
00:00:19,060 --> 00:00:23,870
Pola contra, estamos cubrindo os baleiros
nalgún código pre-existente.

7
00:00:23,870 --> 00:00:28,860
>> O programa find.c solicita números
para cubrir o palheiro, busca o

8
00:00:28,860 --> 00:00:33,260
chea de feno para unha agulla usuario enviou,
e el fai iso chamando clasificar e

9
00:00:33,260 --> 00:00:36,660
busca, funcións definidas
en helpers.c.

10
00:00:36,660 --> 00:00:38,740
Así find.c está escrita xa.

11
00:00:38,740 --> 00:00:41,840
O seu traballo é escribir axudantes.

12
00:00:41,840 --> 00:00:42,940
>> Entón, o que estamos facendo?

13
00:00:42,940 --> 00:00:45,270
Estamos aplicando dúas funcións.

14
00:00:45,270 --> 00:00:50,110
Investigación, que retorna true se un valor
se atopa en palheiro, retornando

15
00:00:50,110 --> 00:00:52,430
false se o valor é
non no palheiro.

16
00:00:52,430 --> 00:00:59,060
E entón nós tamén estamos aplicando especie,
que clasifica o array chamado valores.

17
00:00:59,060 --> 00:01:01,120
Entón, imos afrontar investigación.

18
00:01:01,120 --> 00:01:04,550
>> Busca é aplicado actualmente
como unha busca linear.

19
00:01:04,550 --> 00:01:06,620
Pero pode facer moito mellor do que iso.

20
00:01:06,620 --> 00:01:11,610
Busca linear é aplicada en O de n
tempo, o que é moi lento, aínda que

21
00:01:11,610 --> 00:01:14,920
pode buscar calquera lista que lle é dado.

22
00:01:14,920 --> 00:01:21,190
O seu traballo é a implementación de busca binaria,
que ten tempo de execución O de rexistro n.

23
00:01:21,190 --> 00:01:22,200
Isto é moi rápido.

24
00:01:22,200 --> 00:01:24,240
>> Pero hai unha condición.

25
00:01:24,240 --> 00:01:28,910
Busca binaria só pode buscar
mediante listas pre-ordenada.

26
00:01:28,910 --> 00:01:31,450
Por que isto?

27
00:01:31,450 --> 00:01:33,690
Ben, imos dar un ollo a un exemplo.

28
00:01:33,690 --> 00:01:37,350
Dada unha matriz de valores, o palheiro,
imos estar a ollar

29
00:01:37,350 --> 00:01:41,510
por unha agulla, e neste
exemplo, o número enteiro 3.

30
00:01:41,510 --> 00:01:45,220
>> O xeito que busca binaria funciona é que
compararmos o valor medio de

31
00:01:45,220 --> 00:01:49,430
a matriz para a agulla, así como o xeito no que
abrimos un libro de teléfono para o medio

32
00:01:49,430 --> 00:01:51,720
páxina na Semana 0.

33
00:01:51,720 --> 00:01:55,710
Entón, despois de comparar o valor medio para
a agulla, pode descartar ou a

34
00:01:55,710 --> 00:01:59,620
esquerda ou da metade dereita da matriz
axustado os seus límites.

35
00:01:59,620 --> 00:02:04,450
Neste caso, xa que 3, a agulla, é
inferior a 10, o valor medio, o

36
00:02:04,450 --> 00:02:07,060
certo límite pode diminuír.

37
00:02:07,060 --> 00:02:09,470
>> Pero probe facer os seus límites
tan axustado como sexa posible.

38
00:02:09,470 --> 00:02:12,690
O valor do medio non é a agulla,
entón vostede sabe que non é preciso

39
00:02:12,690 --> 00:02:14,070
inclui-lo na súa procura.

40
00:02:14,070 --> 00:02:18,390
Polo tanto, o seu límite dereito pode usar a
límites da investigación só un pouquiño máis,

41
00:02:18,390 --> 00:02:22,840
e así por diante e así por diante, ata que
atopa a súa agulla.

42
00:02:22,840 --> 00:02:24,580
>> Entón, o que fai o pseudo
código se parece?

43
00:02:24,580 --> 00:02:28,980
Así, mentres que nós aínda estamos mirando a través
a lista e aínda ter

44
00:02:28,980 --> 00:02:33,540
elementos para ollar, tomamos o medio
da lista e comparar isto

45
00:02:33,540 --> 00:02:36,020
valor medio para o noso agulla.

46
00:02:36,020 --> 00:02:38,380
Se son iguais, entón iso significa que temos
atopou a agulla, e podemos

47
00:02:38,380 --> 00:02:40,160
return true.

48
00:02:40,160 --> 00:02:43,940
>> En caso contrario, se a agulla é inferior a
o valor medio, a continuación, isto significa que

49
00:02:43,940 --> 00:02:48,350
pode descartar a metade dereita e só
buscar o lado esquerdo da matriz.

50
00:02:48,350 --> 00:02:51,860
En caso contrario, nós imos buscar o
lado dereito da matriz.

51
00:02:51,860 --> 00:02:55,470
E, ao final, se non ten ningún
máis elementos de esquerda a procura, pero

52
00:02:55,470 --> 00:02:58,030
non atopou a súa agulla aínda,
entón voltar false.

53
00:02:58,030 --> 00:03:02,960
Porque a agulla definitivamente
Non é en palheiro.

54
00:03:02,960 --> 00:03:06,200
>> Agora, unha cousa interesante sobre este pseudo
código en busca binaria é que pode

55
00:03:06,200 --> 00:03:11,000
pode interpretar como un iterativo
ou implantación recursiva.

56
00:03:11,000 --> 00:03:14,900
Polo tanto, sería recursiva se chama
a función de investigación dentro da investigación

57
00:03:14,900 --> 00:03:18,400
funciona en calquera das metades da matriz.

58
00:03:18,400 --> 00:03:20,750
Nós imos cubrir recursão algo
máis tarde no curso.

59
00:03:20,750 --> 00:03:23,210
Pero sei que é unha opción
Se desexa probar.

60
00:03:23,210 --> 00:03:24,460