1
00:00:00,000 --> 00:00:08,532
>> [Музички]

2
00:00:08,532 --> 00:00:12,060
>> ZAMYLA CHAN: Првото нешто што може да
известување за откритие е дека ние веќе

3
00:00:12,060 --> 00:00:13,450
се код напишан за нас.

4
00:00:13,450 --> 00:00:15,160
Ова се нарекува дистрибуција код.

5
00:00:15,160 --> 00:00:18,000
Значи ние не сме само пишување нашите сопствени
кодот од нула повеќе.

6
00:00:18,000 --> 00:00:22,800
Наместо тоа, ние сме пополнување на празнини
во некои постоечки код.

7
00:00:22,800 --> 00:00:27,790
>> На find.c програмата го поттикнува за броеви
да се пополни стогот, пребарувања

8
00:00:27,790 --> 00:00:32,189
haystack за поднесено корисникот игла,
и тоа го прави ова со повикување вид и

9
00:00:32,189 --> 00:00:35,590
пребарување, функции дефинирани
во helpers.c.

10
00:00:35,590 --> 00:00:37,670
Па find.c е напишано веќе.

11
00:00:37,670 --> 00:00:40,770
Вашата работа е да се напише помагачи.

12
00:00:40,770 --> 00:00:41,870
>> Па што правиме ние?

13
00:00:41,870 --> 00:00:44,210
Ние сме спроведување на две функции.

14
00:00:44,210 --> 00:00:49,030
Барај, кој враќа true ако вредност
се наоѓа во стогот, враќајќи се

15
00:00:49,030 --> 00:00:51,370
лажни ако вредноста е
не во haystack.

16
00:00:51,370 --> 00:00:57,990
А потоа ние сме, исто така, спроведување вид
Кои видови на низа наречен вредности.

17
00:00:57,990 --> 00:00:59,960
>> Па ајде да се справи пребарување.

18
00:00:59,960 --> 00:01:04,560
Барај во моментов се спроведува како
линеарно пребарување, но можете да направите многу

19
00:01:04,560 --> 00:01:05,550
подобро од тоа.

20
00:01:05,550 --> 00:01:09,910
Линеарно пребарување се спроведува во О
од n време, што е прилично бавен.

21
00:01:09,910 --> 00:01:13,850
Иако, тоа може да се бара
ниту список даден на него.

22
00:01:13,850 --> 00:01:20,130
Вашата работа е да се имплементира бинарни пребарување,
кој ја стартувате време О на најавите n.

23
00:01:20,130 --> 00:01:21,130
Тоа е доста брзо.

24
00:01:21,130 --> 00:01:23,170
>> Но, има една одредба.

25
00:01:23,170 --> 00:01:27,600
Бинарни пребарување само да направите пребарување
преку пред-сортирани листи.

26
00:01:27,600 --> 00:01:30,370
Зошто е тоа така?

27
00:01:30,370 --> 00:01:32,620
>> Па ајде да погледнеме еден пример.

28
00:01:32,620 --> 00:01:36,280
Дадени низа од вредности, стогот,
ние ќе треба да се бараат

29
00:01:36,280 --> 00:01:37,130
игла.

30
00:01:37,130 --> 00:01:40,460
И во овој пример,
на број три.

31
00:01:40,460 --> 00:01:44,130
Начинот на кој бинарни пребарување работи е дека
ја споредиме на средната вредност на

32
00:01:44,130 --> 00:01:48,370
низата на игла, многу сличен како
ние отвори телефонски именик до средината

33
00:01:48,370 --> 00:01:50,660
страница во недела нула.

34
00:01:50,660 --> 00:01:54,650
>> Па по споредување на средната вредност за
иглата, можете да ги отфрлите или

35
00:01:54,650 --> 00:01:58,530
лево или десната половина на низата
со затегнување на вашиот границите.

36
00:01:58,530 --> 00:02:03,390
Во овој случај, бидејќи три, нашите уши,
е помала од 10, на средната вредност, на

37
00:02:03,390 --> 00:02:05,990
право врзани може да се намали.

38
00:02:05,990 --> 00:02:08,400
Но, обидете се да направите вашиот граници
како цврста како е можно.

39
00:02:08,400 --> 00:02:11,630
Ако средната вредност не е игла,
тогаш знаете дека не треба да се

40
00:02:11,630 --> 00:02:13,010
вклучуваат во вашето пребарување.

41
00:02:13,010 --> 00:02:17,310
Па во право си врзан може да ги заостри
Барај границите само мал малку повеќе,

42
00:02:17,310 --> 00:02:21,770
и така натаму и така натаму се додека
да најдете игла.

43
00:02:21,770 --> 00:02:23,480
>> Значи она што го прави pseudocode изгледа?

44
00:02:23,480 --> 00:02:28,420
Добро, додека ние сме сè уште во потрага преку
листата и се уште имаат елементи за да се

45
00:02:28,420 --> 00:02:33,690
погледне во, ние се на средината на листата,
и споредете дека средна вредност да

46
00:02:33,690 --> 00:02:34,950
нашите игла.

47
00:02:34,950 --> 00:02:37,310
Ако тие се еднакви, тогаш тоа значи дека ние сме
најде игла и можеме да

48
00:02:37,310 --> 00:02:38,990
врати вистина.

49
00:02:38,990 --> 00:02:42,870
>> Инаку, ако иглата е помала од
средната вредност, тогаш тоа значи дека ние

50
00:02:42,870 --> 00:02:47,280
може да ги отфрлите десната половина, и само
пребарување на левата страна на низата.

51
00:02:47,280 --> 00:02:51,090
Инаку, ние ќе се бара
десната страна на низа.

52
00:02:51,090 --> 00:02:54,410
И на крајот, ако не имате било какви
повеќе елементи што останале да пребарување, но ќе

53
00:02:54,410 --> 00:02:58,050
не најдов вашиот игла уште, тогаш ќе
враќање false, бидејќи иглата

54
00:02:58,050 --> 00:03:01,890
дефинитивно не е во haystack.

55
00:03:01,890 --> 00:03:05,270
>> Сега уредни нешто во врска со овој pseudocode
во бинарна пребарување е тоа што може да биде

56
00:03:05,270 --> 00:03:09,940
толкува како било итеративен
или рекурзивен имплементација.

57
00:03:09,940 --> 00:03:13,810
Па тоа ќе биде рекурзивен ако наречен
функцијата за пребарување во рамките на пребарувањето

58
00:03:13,810 --> 00:03:17,350
функционираат на двете половина на низата.

59
00:03:17,350 --> 00:03:21,030
Ние ќе ги покрие рекурзија малку подоцна во
се разбира, но знам дека тоа е

60
00:03:21,030 --> 00:03:24,190
опција ако сакате да се обидете.

61
00:03:24,190 --> 00:03:26,030
>> Сега ајде да ги погледнеме во вид.

62
00:03:26,030 --> 00:03:30,750
Вид зема низа и цел број
n, која е со големина на низа.

63
00:03:30,750 --> 00:03:34,030
Сега постојат различни видови
на сорти, и може да се погледне во некои

64
00:03:34,030 --> 00:03:36,370
шорцеви за демонстрации и објаснувања.

65
00:03:36,370 --> 00:03:39,580
Враќање тип за нашите
функција вид е неважечки.

66
00:03:39,580 --> 00:03:43,580
Па тоа значи дека ние нема
да се врати било низа од вид.

67
00:03:43,580 --> 00:03:48,140
Ние сме всушност ќе се смени многу
низа што беше донесен во нас.

68
00:03:48,140 --> 00:03:52,290
>> И тоа е можно, бидејќи низи се
донесени од страна на референтни во C. Сега ќе

69
00:03:52,290 --> 00:03:55,290
види повеќе за ова подоцна, но
суштинска разлика помеѓу донесувањето

70
00:03:55,290 --> 00:03:59,340
во нешто како цел број и донесување
во низа, е дека кога ќе

71
00:03:59,340 --> 00:04:03,490
помине во цел број, C е само ќе
направи копија на таа цел број и да го положат

72
00:04:03,490 --> 00:04:04,450
до функција.

73
00:04:04,450 --> 00:04:08,530
Оригиналната променлива нема да бидат променети
Откако функција е завршена.

74
00:04:08,530 --> 00:04:12,480
Со низа, од друга страна, тоа е
нема да направи копија, и ќе

75
00:04:12,480 --> 00:04:17,910
всушност се уредување на
себе многу низа.

76
00:04:17,910 --> 00:04:21,269
>> Така еден вид на вид е
вид селекција.

77
00:04:21,269 --> 00:04:24,750
Вид на селекција работи со почеток во
на почетокот, а потоа ќе iterate

78
00:04:24,750 --> 00:04:26,820
над и да се најде најмалиот елемент.

79
00:04:26,820 --> 00:04:30,710
А потоа ќе трампа дека најмалите
елемент со првиот.

80
00:04:30,710 --> 00:04:34,360
А потоа ќе се преселат во вториот елемент
, Се најде на следната најмалиот

81
00:04:34,360 --> 00:04:38,320
елемент, а потоа се разменуваат дека со
Вториот елемент во низата бидејќи

82
00:04:38,320 --> 00:04:41,100
првиот елемент е веќе подредени.

83
00:04:41,100 --> 00:04:45,370
И така, тогаш ќе продолжи за секој
елемент во идентификување на најмалите

84
00:04:45,370 --> 00:04:47,690
вредност и Замена на тоа надвор.

85
00:04:47,690 --> 00:04:53,460
>> Зашто Јас еднаква на 0, првиот елемент
до n минус 1, си оди за да се споредат

86
00:04:53,460 --> 00:04:57,820
секој нареден вредност после тоа и да се најде
индексот на минималната вредност.

87
00:04:57,820 --> 00:05:02,520
Откако ќе се најдат на индексот минималната вредност,
можете да го трампа дека вредноста на низа

88
00:05:02,520 --> 00:05:05,930
минимум и низа I.

89
00:05:05,930 --> 00:05:09,760
>> Друг тип на вид што можете да
спроведување е балон вид.

90
00:05:09,760 --> 00:05:14,380
Значи меур вид iterates преку листа
споредување соседните елементи и

91
00:05:14,380 --> 00:05:17,720
Замена на елементи кои
се во погрешна цел.

92
00:05:17,720 --> 00:05:22,380
И на овој начин, најголемиот елемент
ќе меур до крај.

93
00:05:22,380 --> 00:05:28,070
И листата е сортирана еднаш не повеќе
елементи биле заменети.

94
00:05:28,070 --> 00:05:31,920
>> Значи тоа се два примери на сортирање
алгоритми кои може да се спроведе за

95
00:05:31,920 --> 00:05:33,230
програмата најдете.

96
00:05:33,230 --> 00:05:37,350
Откако ќе завршите вид, и сте
направи за пребарување, ќе завршиш.

97
00:05:37,350 --> 00:05:39,720
Моето име е Zamyla, а тоа е CS50.

98
00:05:39,720 --> 00:05:46,987
>> [Музички]