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
Купа сено за потребител предостави игла,
и да го прави това, като се обадите на сортиране и

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
Search, която връща истина, ако стойността
се намира в купа сено, връщайки

15
00:00:49,030 --> 00:00:51,370
невярно, ако стойността е
не в купа сено.

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
Linear търсене се осъществява в O
п време, което е доста бавно.

21
00:01:09,910 --> 00:01:13,850
Въпреки, че може да търси
всеки списък, дадено му.

22
00:01:13,850 --> 00:01:20,130
Вашата работа е да се приложат двоично търсене,
която тече в момента O на дневник п.

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
Binary търсене може да търси само
чрез предварително сортирани списъци.

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
не са намерили своя игла все още, тогава ще
връщане фалшиви защото иглата

54
00:02:58,050 --> 00:03:01,890
определено не е в купа сено.

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
Sort отнема масив и цялото число
п, което е дължината на масива.

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
Подреди подбор работи като започнете
началото, а след това ви обхождане

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, на много първи елемент
до п минус 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
Така балон подреди итерации над списъка
сравняване на съседни елементи и

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
>> [За възпроизвеждане на музика]