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

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Hej, jag är Rob.

3
00:00:15,010 --> 00:00:16,790
Hur vi använder en binär sökning?

4
00:00:16,790 --> 00:00:18,770
Låt oss ta reda på.

5
00:00:18,770 --> 00:00:23,400
Så, notera att sökningen ska vi
att genomföra rekursivt.

6
00:00:23,400 --> 00:00:27,470
Du kan också implementera binär sökning
iterativt, så om du gjorde det,

7
00:00:27,470 --> 00:00:29,280
det är väl bra.

8
00:00:29,280 --> 00:00:32,820
>> Nu först, låt oss komma ihåg vad
parametrar till sökningen är tänkt att vara.

9
00:00:32,820 --> 00:00:36,120
Här ser vi int värde, vilket är
tänkt att vara det värde användaren är

10
00:00:36,120 --> 00:00:37,320
efter.

11
00:00:37,320 --> 00:00:40,800
Vi ser int värden arrayen, vilket
är arrayen där vi är

12
00:00:40,800 --> 00:00:42,520
söker efter värde.

13
00:00:42,520 --> 00:00:45,602
Och vi ser int n, vilket är
längden på vår array.

14
00:00:45,602 --> 00:00:47,410
>> Nu, först sak först.

15
00:00:47,410 --> 00:00:51,350
Vi kontrollerar om n är lika med 0, i
vilket fall vi returnera false.

16
00:00:51,350 --> 00:00:54,770
Det är bara att om vi har en tom
array värde är uppenbarligen inte i en

17
00:00:54,770 --> 00:00:57,860
tom array, så att vi kan returnera false.

18
00:00:57,860 --> 00:01:01,250
>> Nu, vi faktiskt vill göra det binära
Sök del av binär sökning.

19
00:01:01,250 --> 00:01:04,780
Så, vi vill hitta mitt
inslag i denna samling.

20
00:01:04,780 --> 00:01:09,130
Här säger vi mitt lika n delas
genom två, sedan mitten elementet är

21
00:01:09,130 --> 00:01:12,240
kommer att vara längden på
vår samling delat med 2.

22
00:01:12,240 --> 00:01:15,040
Nu ska vi kontrollera om det
mellersta del är lika med värdet vi är

23
00:01:15,040 --> 00:01:16,160
efter.

24
00:01:16,160 --> 00:01:21,030
Så om värden mitten lika värde, vi
kan returnera sant eftersom vi hittat

25
00:01:21,030 --> 00:01:22,810
värde i vår samling.

26
00:01:22,810 --> 00:01:26,380
>> Men om det inte var sant, nu
vi behöver göra den rekursiva

27
00:01:26,380 --> 00:01:27,840
steget med binär sökning.

28
00:01:27,840 --> 00:01:30,450
Vi måste söka antingen till
kvar i matrisen eller till den

29
00:01:30,450 --> 00:01:32,320
mitten av uppsättningen.

30
00:01:32,320 --> 00:01:39,280
Så här säger vi om värden vid mitten är
mindre än värdet, innebär att det värdet

31
00:01:39,280 --> 00:01:41,350
var större än den mellersta
av arrayen.

32
00:01:41,350 --> 00:01:45,790
Så värdet måste vara till höger om den
faktor som vi bara tittade på.

33
00:01:45,790 --> 00:01:48,090
>> Så här kommer vi att
sök rekursivt.

34
00:01:48,090 --> 00:01:50,320
Och ska vi titta på vad vi passerar
till detta i en sekund.

35
00:01:50,320 --> 00:01:53,440
Men vi kommer att söka till
höger om den mellersta elementet.

36
00:01:53,440 --> 00:01:57,710
Och i det andra fallet, innebär det att
värde var lägre än i mitten av

37
00:01:57,710 --> 00:02:00,660
array, och så ska vi
att söka till vänster.

38
00:02:00,660 --> 00:02:03,520
Nu är den vänstra kommer att vara
lite lättare att titta på.

39
00:02:03,520 --> 00:02:07,770
Så ser vi här att vi är rekursivt
ringer ökning där den första

40
00:02:07,770 --> 00:02:10,120
argumentet är, återigen, det värde
vi ser över.

41
00:02:10,120 --> 00:02:14,970
Det andra argumentet är att vara den
array som vi sökte över.

42
00:02:14,970 --> 00:02:17,090
Och det sista elementet är nu mitt.

43
00:02:17,090 --> 00:02:21,650
Kom ihåg att den sista parametern är vår int
n, så det är längden på vår samling.

44
00:02:21,650 --> 00:02:25,310
>> I rekursivt anrop för att söka, vi är
nu säga att längden av den

45
00:02:25,310 --> 00:02:27,230
array är mitt.

46
00:02:27,230 --> 00:02:32,900
Så, om vår samling var i storlek 20 och vi
sökte på index 10, eftersom mitt är

47
00:02:32,900 --> 00:02:36,930
20 delat med 2, gör att vi är
passerar 10 som ny

48
00:02:36,930 --> 00:02:38,300
längden på vår array.

49
00:02:38,300 --> 00:02:41,910
Kom ihåg att när du har en array
med längd 10, innebär att den giltiga

50
00:02:41,910 --> 00:02:45,450
elementen är i index 0 till 9.

51
00:02:45,450 --> 00:02:50,120
Så det här är precis vad vi vill
specificera vår uppdaterade samling - vänster

52
00:02:50,120 --> 00:02:53,010
array från mittelementet.

53
00:02:53,010 --> 00:02:55,710
>> Så, titta till höger är
lite svårare.

54
00:02:55,710 --> 00:03:00,170
Nu först, låt oss betrakta längden
av uppsättningen till höger om den

55
00:03:00,170 --> 00:03:01,240
mellanelementet.

56
00:03:01,240 --> 00:03:08,390
Så, om vår array var av storlek n, då
ny samling kommer att vara av storlek n minus

57
00:03:08,390 --> 00:03:10,140
mitt minus 1.

58
00:03:10,140 --> 00:03:12,530
Så, låt oss tänka på n minus mitten.

59
00:03:12,530 --> 00:03:18,710
>> Återigen, om matrisen var av storlek 20 och
vi delar med 2 för att få en mitt,

60
00:03:18,710 --> 00:03:23,540
så i mitten är 10, då n minus mitten
kommer att ge oss 10, så 10

61
00:03:23,540 --> 00:03:25,330
element till höger om mitten.

62
00:03:25,330 --> 00:03:27,780
Men vi har också denna minus
1, eftersom vi inte vill

63
00:03:27,780 --> 00:03:29,700
inkluderar mitten självt.

64
00:03:29,700 --> 00:03:34,190
Så n minus mitten minus 1 ger oss
totala antalet element till höger

65
00:03:34,190 --> 00:03:36,800
av mitt index i arrayen.

66
00:03:36,800 --> 00:03:41,870
>> Nu här, kom ihåg att mitt
parametern är värden array.

67
00:03:41,870 --> 00:03:46,180
Så här, vi passerar en
uppdaterade värden array.

68
00:03:46,180 --> 00:03:50,930
Dessa värden plus mitt plus 1 är
faktiskt säger rekursivt ringa

69
00:03:50,930 --> 00:03:56,460
sök, som passerar i en ny array, där
att ny array börjar i mitten

70
00:03:56,460 --> 00:03:59,370
plus en av våra ursprungliga värden array.

71
00:03:59,370 --> 00:04:05,400
>> En alternativ syntax för det, nu när
du har börjat se pekare, är

72
00:04:05,400 --> 00:04:10,170
et-värden mitten plus ett.

73
00:04:10,170 --> 00:04:17,149
Så, ta adressen till den mellersta
plus en del av värden.

74
00:04:17,149 --> 00:04:23,690
>> Nu, om du inte var bekväm
modifiera en matris som detta, du

75
00:04:23,690 --> 00:04:28,900
kunde också ha genomfört detta med
en rekursiv hjälparfunktion, där

76
00:04:28,900 --> 00:04:31,680
att hjälparfunktion tar
fler argument.

77
00:04:31,680 --> 00:04:36,610
Så i stället för att bara värde, desto
array, och storleken på matrisen,

78
00:04:36,610 --> 00:04:42,315
hjälpare funktion skulle ta mer
argument, bland annat lägre index

79
00:04:42,315 --> 00:04:45,280
att du skulle bry sig om i arrayen
och den övre index att du bryr dig

80
00:04:45,280 --> 00:04:46,300
om uppsättningen.

81
00:04:46,300 --> 00:04:49,770
>> Och så hålla reda på både den nedre
index och den övre index, gör du inte

82
00:04:49,770 --> 00:04:52,780
behöver någonsin ändra
ursprungliga värdena array.

83
00:04:52,780 --> 00:04:56,390
Du kan bara fortsätta att
använda värden array.

84
00:04:56,390 --> 00:04:59,540
Men här, märker vi inte behöver en hjälpare
fungera så länge som vi är

85
00:04:59,540 --> 00:05:01,760
villig att ändra den ursprungliga
värden array.

86
00:05:01,760 --> 00:05:05,020
Vi är villiga att gå in
en uppdaterad värden.

87
00:05:05,020 --> 00:05:09,140
>> Nu kan vi inte binär sökning över
en array som är osorterade.

88
00:05:09,140 --> 00:05:12,220
Så, låt oss få detta redas ut.

89
00:05:12,220 --> 00:05:17,650
Nu märker det slaget är förbi två
parametrar int värden, som är den

90
00:05:17,650 --> 00:05:21,110
array som vi sorterar, och int n,
vilken är längden av den matris som

91
00:05:21,110 --> 00:05:22,250
vi sortering.

92
00:05:22,250 --> 00:05:24,840
Så här vill vi att genomföra
en sorteringsalgoritm

93
00:05:24,840 --> 00:05:26,690
som är o n i kvadrat.

94
00:05:26,690 --> 00:05:30,560
Du kan välja bubbla sortera, val
sortera eller inser sortera eller

95
00:05:30,560 --> 00:05:32,670
någon annan form har vi inte
ses i klassen.

96
00:05:32,670 --> 00:05:36,380
Men här kommer vi till
använda val sort.

97
00:05:36,380 --> 00:05:40,030
>> Så kommer vi att iterera
över hela antenn.

98
00:05:40,030 --> 00:05:44,360
Tja, här ser vi att vi iteration
från 0 till n minus 1.

99
00:05:44,360 --> 00:05:45,990
Varför inte hela vägen upp till n?

100
00:05:45,990 --> 00:05:49,320
Tja, om vi redan har sorterat det första
n minus 1 element, då den

101
00:05:49,320 --> 00:05:54,420
mycket sista elementet vad måste redan vara
på rätt plats, så sortering över

102
00:05:54,420 --> 00:05:56,520
hela arrayen.

103
00:05:56,520 --> 00:05:58,770
>> Nu, kom ihåg hur urvalet
sorterings fungerar.

104
00:05:58,770 --> 00:06:01,950
Vi kommer att gå över hela antenn
söker det minsta värdet i

105
00:06:01,950 --> 00:06:04,480
matrisen och stick som
vid början.

106
00:06:04,480 --> 00:06:07,610
Sen ska vi gå över hela
array igen efter den andra

107
00:06:07,610 --> 00:06:10,410
minsta elementet, och stick som
i den andra positionen i

108
00:06:10,410 --> 00:06:12,100
array, och så vidare.

109
00:06:12,100 --> 00:06:14,330
Så, det är vad det gör.

110
00:06:14,330 --> 00:06:17,290
>> Här ser vi att vi är
inställning av nuvarande minimi

111
00:06:17,290 --> 00:06:20,030
värde till den i: te indexet.

112
00:06:20,030 --> 00:06:23,160
Så på den första iterationen, vi ska
att överväga minimivärdet att vara

113
00:06:23,160 --> 00:06:25,030
början av vår samling.

114
00:06:25,030 --> 00:06:28,500
Sedan kommer vi att iterera över
återstoden av arrayen, kontrollera för att

115
00:06:28,500 --> 00:06:31,870
se om det några element som är mindre än
det som vi är idag

116
00:06:31,870 --> 00:06:33,900
med tanke på den minsta.

117
00:06:33,900 --> 00:06:38,840
>> Så här värderar j plus en - det är
mindre än vad vi är idag

118
00:06:38,840 --> 00:06:40,380
med tanke på den minsta.

119
00:06:40,380 --> 00:06:42,940
Sen ska vi uppdatera vad
vi tycker är det minsta till

120
00:06:42,940 --> 00:06:44,640
index j plus en.

121
00:06:44,640 --> 00:06:48,540
Så, gör det över hela matrisen,
och efter detta for-loop, minimum

122
00:06:48,540 --> 00:06:53,160
bör vara det minsta elementet från
den i: te positionen i arrayen.

123
00:06:53,160 --> 00:06:57,350
>> När vi har det, kan vi byta
minimivärde i den i: te positionen

124
00:06:57,350 --> 00:06:58,230
i arrayen.

125
00:06:58,230 --> 00:07:00,130
Så det här är bara en vanlig swap.

126
00:07:00,130 --> 00:07:03,940
Vi lagrar i ett tillfälligt värde -
det i: te värdet i matrisen -

127
00:07:03,940 --> 00:07:08,460
sätta i den i: te värdet i matrisen den
minimivärde som hör hemma där,

128
00:07:08,460 --> 00:07:13,580
och sedan lagra tillbaka in där
nuvarande minimivärde brukade vara

129
00:07:13,580 --> 00:07:16,460
i: te värdet i matrisen, så
att vi inte förlorar det.

130
00:07:16,460 --> 00:07:20,510
>> Så fortsätter det på
nästa iteration.

131
00:07:20,510 --> 00:07:23,480
Vi kommer att börja leta efter den andra
lägsta värdet och sätt in det i

132
00:07:23,480 --> 00:07:24,590
andra positionen.

133
00:07:24,590 --> 00:07:27,440
På tredje iteration, kommer vi att titta efter
den tredje minsta värde och insats

134
00:07:27,440 --> 00:07:31,550
som i den tredje positionen, och så
på tills vi har en sorterad array.

135
00:07:31,550 --> 00:07:33,820
Mitt namn är Rob, och detta
var val sort.

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