1
00:00:00,000 --> 00:00:13,300

2
00:00:13,300 --> 00:00:15,010
>> Роб BOWDEN: Здраво, јас сум Роб.

3
00:00:15,010 --> 00:00:16,790
Како ние да вработуваат бинарни пребарување?

4
00:00:16,790 --> 00:00:18,770
Ајде да дознаете.

5
00:00:18,770 --> 00:00:23,400
Така, имајте во предвид дека ова пребарување одиме
за спроведување на рекурзивно.

6
00:00:23,400 --> 00:00:27,470
Можете исто така би можеле да спроведат бинарни пребарување
iteratively, па ако го направи тоа,

7
00:00:27,470 --> 00:00:29,280
тоа е совршено добро.

8
00:00:29,280 --> 00:00:32,820
>> Сега на прво место, ајде да се сетам што
параметри за пребарување, се со цел да биде.

9
00:00:32,820 --> 00:00:36,120
Тука, ние гледаме int вредност, која е
би требало да биде вредноста на корисникот е

10
00:00:36,120 --> 00:00:37,320
барате.

11
00:00:37,320 --> 00:00:40,800
Можеме да видиме на int вредности низа, која
е низа во која ние сме

12
00:00:40,800 --> 00:00:42,520
во потрага по вредност.

13
00:00:42,520 --> 00:00:45,602
И гледаме цел број n, која е
времетраењето на нашите низа.

14
00:00:45,602 --> 00:00:47,410
>> Сега, прво нешто што прво.

15
00:00:47,410 --> 00:00:51,350
Ние се провери да се види дали N еднаква на 0, во
кој случај ние се врати лажни.

16
00:00:51,350 --> 00:00:54,770
Тоа е само велејќи, ако имаме празен
низа, вредност не е јасно во

17
00:00:54,770 --> 00:00:57,860
празна низа, така што може да се врати лажни.

18
00:00:57,860 --> 00:01:01,250
>> Сега, ние всушност сакате да го направите бинарна
Барај дел од бинарни пребарување.

19
00:01:01,250 --> 00:01:04,780
Значи, ние сакаме да се најде на средината
елемент на оваа низа.

20
00:01:04,780 --> 00:01:09,130
Тука, ние се каже средината еднаква N поделени
од 2, од средината елемент е

21
00:01:09,130 --> 00:01:12,240
ќе биде должината на
нашите низа поделено со 2.

22
00:01:12,240 --> 00:01:15,040
Сега ние ќе треба да се провери да се види дали
средината елемент е еднаква на вредноста ние сме

23
00:01:15,040 --> 00:01:16,160
барате.

24
00:01:16,160 --> 00:01:21,030
Па ако вредностите средината еднаква вредност, ние
може да се врати точно бидејќи ние откривме

25
00:01:21,030 --> 00:01:22,810
вредност во нашата низа.

26
00:01:22,810 --> 00:01:26,380
>> Но, ако тоа не е вистина, сега
ние треба да направите рекурзивен

27
00:01:26,380 --> 00:01:27,840
чекор на бинарни пребарување.

28
00:01:27,840 --> 00:01:30,450
Ние треба да се бараат или на
лево од низа или до

29
00:01:30,450 --> 00:01:32,320
средината на низата.

30
00:01:32,320 --> 00:01:39,280
Па еве, ние се каже ако вредностите на средината е
помалку од вредноста, што значи дека вредност

31
00:01:39,280 --> 00:01:41,350
е поголема од средината
на низата.

32
00:01:41,350 --> 00:01:45,790
Значи вредност мора да биде на правото на
елемент кој ние само погледна.

33
00:01:45,790 --> 00:01:48,090
>> Па еве, ние ќе
пребарување рекурзивно.

34
00:01:48,090 --> 00:01:50,320
И ние ќе се погледне во она што го поминува
тоа во вториот.

35
00:01:50,320 --> 00:01:53,440
Но ние ќе се бара на
правото на средината елемент.

36
00:01:53,440 --> 00:01:57,710
И во другиот случај, тоа значи дека
вредноста беше помала од средината на

37
00:01:57,710 --> 00:02:00,660
низа, и така ние ќе
за пребарување на лево.

38
00:02:00,660 --> 00:02:03,520
Сега, по левата страна ќе биде
малку полесно да се погледне.

39
00:02:03,520 --> 00:02:07,770
Значи, гледаме дека тука сме рекурзивно
повикувајќи пребарување каде што првиот

40
00:02:07,770 --> 00:02:10,120
аргумент е, пак, вредноста
ние сме во потрага завршена.

41
00:02:10,120 --> 00:02:14,970
Вториот аргумент ќе биде
низа што бевме во потрага завршена.

42
00:02:14,970 --> 00:02:17,090
А последниот елемент сега е средината.

43
00:02:17,090 --> 00:02:21,650
Се сеќавам на последниот параметар е нашата int
n, па тоа е должината на нашите низа.

44
00:02:21,650 --> 00:02:25,310
>> Во рекурзивен повик да се бараат, ние сме
сега велат дека должината на

45
00:02:25,310 --> 00:02:27,230
низа е средината.

46
00:02:27,230 --> 00:02:32,900
Значи, ако нашите низа беше на големина 20 и
пребаруваат на индекс 10, бидејќи средината е

47
00:02:32,900 --> 00:02:36,930
20 поделено со 2, што значи дека ние сме
кој поминува 10 како нови

48
00:02:36,930 --> 00:02:38,300
должината на нашите низа.

49
00:02:38,300 --> 00:02:41,910
Се сеќавам дека кога ќе имаат низа
должина 10, тоа значи дека важи

50
00:02:41,910 --> 00:02:45,450
елементи се во индекси од 0 до 9.

51
00:02:45,450 --> 00:02:50,120
Значи ова е токму она што сакате да го
наведете нашите ажурирани низа - по левата страна

52
00:02:50,120 --> 00:02:53,010
низа од средината елемент.

53
00:02:53,010 --> 00:02:55,710
>> Значи, во потрага на правото е
малку потешко.

54
00:02:55,710 --> 00:03:00,170
Сега на прво место, ајде да се разгледа должината
на низата на правото на

55
00:03:00,170 --> 00:03:01,240
средината елемент.

56
00:03:01,240 --> 00:03:08,390
Значи, ако нашите низа беше на големина n, тогаш
нова низа ќе биде на големина n минус

57
00:03:08,390 --> 00:03:10,140
средината минус 1.

58
00:03:10,140 --> 00:03:12,530
Значи, ајде да мислам на n минус средината.

59
00:03:12,530 --> 00:03:18,710
>> Повторно, ако низата беа на големина 20
ние подели со 2 за да го добиете средината,

60
00:03:18,710 --> 00:03:23,540
па средината е 10, тогаш n минус средината
се случува да ни даде 10, па 10

61
00:03:23,540 --> 00:03:25,330
елементи на правото на средината.

62
00:03:25,330 --> 00:03:27,780
Но, ние исто така имаат оваа минус
1, бидејќи ние не сакаме да

63
00:03:27,780 --> 00:03:29,700
вклучуваат средината себе.

64
00:03:29,700 --> 00:03:34,190
Па n минус средината минус 1 нас дава
вкупниот број на елементи на правото

65
00:03:34,190 --> 00:03:36,800
на средината индекс во низа.

66
00:03:36,800 --> 00:03:41,870
>> Сега тука, се сеќавам дека средината
параметар е вредностите низа.

67
00:03:41,870 --> 00:03:46,180
Па еве, ние сме полагање на
нема вредности низа.

68
00:03:46,180 --> 00:03:50,930
Ова вредности плус средината плус 1 е
всушност се вели рекурзивно се јавите

69
00:03:50,930 --> 00:03:56,460
пребарување, преминува во нова низа, каде
дека нова низа започнува во средината

70
00:03:56,460 --> 00:03:59,370
плус еден од нашите оригинални вредности низа.

71
00:03:59,370 --> 00:04:05,400
>> Една алтернативна синтакса за тоа, сега дека
сте почнале да ја видите покажувачи, е

72
00:04:05,400 --> 00:04:10,170
симболот вредности средината плус 1.

73
00:04:10,170 --> 00:04:17,149
Значи, го дофати адресата на средината
плус еден елемент на вредности.

74
00:04:17,149 --> 00:04:23,690
>> Сега, ако не беа удобно
менување низа, како што,

75
00:04:23,690 --> 00:04:28,900
исто така може да се спроведува оваа помош
рекурзивен помошна функција, каде што

76
00:04:28,900 --> 00:04:31,680
дека помошна функција се
повеќе аргументи.

77
00:04:31,680 --> 00:04:36,610
Така, наместо за преземање само на вредност,
низа, а големината на низата,

78
00:04:36,610 --> 00:04:42,315
помошник функција може да трае повеќе
аргументи, вклучувајќи го и понизок индекс

79
00:04:42,315 --> 00:04:45,280
кои ќе се грижат за во низа
и горниот индекс, кој ти е гајле

80
00:04:45,280 --> 00:04:46,300
за низа.

81
00:04:46,300 --> 00:04:49,770
>> И така следење на двете пониски
индекс и горниот индекс, вие не

82
00:04:49,770 --> 00:04:52,780
треба да некогаш менување на
оригинални вредности низа.

83
00:04:52,780 --> 00:04:56,390
Можете едноставно да продолжите да
користете вредности низа.

84
00:04:56,390 --> 00:04:59,540
Но, тука, информации ние не треба помошник
функционираат како долго како што се

85
00:04:59,540 --> 00:05:01,760
подготвени за менување на оригиналниот
вредности низа.

86
00:05:01,760 --> 00:05:05,020
Ние сме подготвени да се помине во
ажурирани вредности.

87
00:05:05,020 --> 00:05:09,140
>> Сега, ние не може бинарни пребарување над
низа што е вон.

88
00:05:09,140 --> 00:05:12,220
Значи, ајде да добиете оваа решат.

89
00:05:12,220 --> 00:05:17,650
Сега, да се забележи дека вид е изминатите две
параметри int вредности, кое е

90
00:05:17,650 --> 00:05:21,110
низа, дека ние сме сортирање и int n,
кое е должината на низа која

91
00:05:21,110 --> 00:05:22,250
ние сме сортирање.

92
00:05:22,250 --> 00:05:24,840
Значи, тука сакаме да се имплементира
на сортирање алгоритам

93
00:05:24,840 --> 00:05:26,690
што е o на n квадрат.

94
00:05:26,690 --> 00:05:30,560
Можете да изберете меур вид, селекција
вид, или вметнување вид, или

95
00:05:30,560 --> 00:05:32,670
некои други вид немаме
виден во класата.

96
00:05:32,670 --> 00:05:36,380
Но, овде, ние ќе
го користите селекција вид.

97
00:05:36,380 --> 00:05:40,030
>> Значи, ние ќе iterate
во текот на целата низа.

98
00:05:40,030 --> 00:05:44,360
Добро, тука можеме да видиме дека ние сме процесирањето
од 0 до n минус 1.

99
00:05:44,360 --> 00:05:45,990
Зошто не сите на патот до n?

100
00:05:45,990 --> 00:05:49,320
Па, ако веќе сме подредени на првиот
n минус 1 елементи, тогаш

101
00:05:49,320 --> 00:05:54,420
Многу последниот елемент што веќе мора да биде
во правилната место, па сортирање над

102
00:05:54,420 --> 00:05:56,520
целата низа.

103
00:05:56,520 --> 00:05:58,770
>> Сега, се сеќавам како избор
вид работи.

104
00:05:58,770 --> 00:06:01,950
Ние ќе одиме во текот на целата низа
во потрага по минималната вредност во

105
00:06:01,950 --> 00:06:04,480
низа и стап кој
на почетокот.

106
00:06:04,480 --> 00:06:07,610
Тогаш ние ќе одиме во текот на целиот
низа повторно во потрага по втората

107
00:06:07,610 --> 00:06:10,410
најмалиот елемент, и стап кој
во втората позиција во

108
00:06:10,410 --> 00:06:12,100
низа, и така натаму.

109
00:06:12,100 --> 00:06:14,330
Значи, тоа е она што овој го прави.

110
00:06:14,330 --> 00:06:17,290
>> Тука, ние сме сведоци дека ние сме
поставување на тековната минимум

111
00:06:17,290 --> 00:06:20,030
вредност на i-тиот индекс.

112
00:06:20,030 --> 00:06:23,160
Па на првата итерација, ние ќе
да се разгледа на минималната вредност да биде

113
00:06:23,160 --> 00:06:25,030
почетокот на нашата низа.

114
00:06:25,030 --> 00:06:28,500
Тогаш, ние ќе iterate преку
остатокот од низата, проверка за да

115
00:06:28,500 --> 00:06:31,870
види дали има било какви елементи помали од
оној што ние сме во моментов

116
00:06:31,870 --> 00:06:33,900
со оглед на минимум.

117
00:06:33,900 --> 00:06:38,840
>> Па еве, вредности ѕ плус еден - тоа е
помалку од она што ние сме во моментов

118
00:06:38,840 --> 00:06:40,380
со оглед на минимум.

119
00:06:40,380 --> 00:06:42,940
Тогаш ние ќе треба да се ажурира што
мислиме дека е минимум за да

120
00:06:42,940 --> 00:06:44,640
индекс ѕ плус 1.

121
00:06:44,640 --> 00:06:48,540
Значи, го направи тоа низ целата низа,
и по овој за телефонска линија, минимум

122
00:06:48,540 --> 00:06:53,160
треба да биде минимално елемент од
позицијата i-тиот во низа.

123
00:06:53,160 --> 00:06:57,350
>> Откако ќе го имаме тоа, ние може да се трампа на
минималната вредност во I-та позиција

124
00:06:57,350 --> 00:06:58,230
во низа.

125
00:06:58,230 --> 00:07:00,130
Па ова е само стандарден swap.

126
00:07:00,130 --> 00:07:03,940
Ние се сместат во привремени вредност -
i-тиот вредност во низа -

127
00:07:03,940 --> 00:07:08,460
стави во i-тиот вредност во низа на
минималната вредност која припаѓа таму,

128
00:07:08,460 --> 00:07:13,580
а потоа да се сместат назад во која
тековните минимална вредност се користи за да биде

129
00:07:13,580 --> 00:07:16,460
i-тиот вредност во низа, така
дека ние не го изгуби.

130
00:07:16,460 --> 00:07:20,510
>> Значи, кој го продолжува
следниот повторување.

131
00:07:20,510 --> 00:07:23,480
Ќе почнете да барате вториот
минималната вредност и вметнете дека во

132
00:07:23,480 --> 00:07:24,590
втората позиција.

133
00:07:24,590 --> 00:07:27,440
На третиот повторување, ние ќе се погледне за
третиот минималната вредност и вметнете

134
00:07:27,440 --> 00:07:31,550
дека во третата позиција, и така
се додека имаме сортирани низа.

135
00:07:31,550 --> 00:07:33,820
Моето име е Роб, и ова
беше изборот вид.

136
00:07:33,820 --> 00:07:39,456