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

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Cześć, jestem Rob.

3
00:00:15,010 --> 00:00:16,790
Jak zatrudniamy binarnego wyszukiwania?

4
00:00:16,790 --> 00:00:18,770
Przekonajmy się.

5
00:00:18,770 --> 00:00:23,400
Tak więc należy pamiętać, że to wyszukiwanie jedziemy
wdrożyć rekurencyjnie.

6
00:00:23,400 --> 00:00:27,470
Można też zaimplementować wyszukiwanie binarne
iteracyjnie, więc jeśli to zrobił,

7
00:00:27,470 --> 00:00:29,280
to jest całkowicie w porządku.

8
00:00:29,280 --> 00:00:32,820
>> Teraz pierwsze, pamiętajmy, co
parametry wyszukiwania mają być.

9
00:00:32,820 --> 00:00:36,120
Tutaj widzimy wartość int, który jest
powinna być wartość użytkownika

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

11
00:00:37,320 --> 00:00:40,800
Widzimy tablicę wartości int, które
jest tablicą, w której jesteśmy

12
00:00:40,800 --> 00:00:42,520
poszukiwanie wartości.

13
00:00:42,520 --> 00:00:45,602
I widzimy, int n, która jest
Długość naszego układu.

14
00:00:45,602 --> 00:00:47,410
>> Teraz pierwsza rzecz pierwsza.

15
00:00:47,410 --> 00:00:51,350
Sprawdzamy, czy n jest równe 0, w
takim przypadku zwracamy false.

16
00:00:51,350 --> 00:00:54,770
To tylko, że jeśli mamy pusty
tablica, wartość wyraźnie nie jest w

17
00:00:54,770 --> 00:00:57,860
pusta tablica, więc możemy wrócić fałszywe.

18
00:00:57,860 --> 00:01:01,250
>> Teraz, tak naprawdę chcą zrobić binarne
szukaj częścią poszukiwania binarnego.

19
00:01:01,250 --> 00:01:04,780
Tak, chcemy znaleźć w środku
Element tej tablicy.

20
00:01:04,780 --> 00:01:09,130
Tutaj mówimy, jest równa n dzieli średnim
od 2, gdyż Element środkowy jest

21
00:01:09,130 --> 00:01:12,240
Będzie długość
Nasza tablica podzielić przez 2.

22
00:01:12,240 --> 00:01:15,040
Teraz mamy zamiar sprawdzić, czy
środkowy element jest równa wartości jesteśmy

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

24
00:01:16,160 --> 00:01:21,030
Tak więc, jeśli wartość jest równa wartości środkowe, my
może wrócić prawda od znaleźliśmy

25
00:01:21,030 --> 00:01:22,810
wartość w naszej tablicy.

26
00:01:22,810 --> 00:01:26,380
>> Ale jeśli to nie była prawda, teraz
musimy zrobić rekurencyjnego

27
00:01:26,380 --> 00:01:27,840
etap poszukiwania binarnego.

28
00:01:27,840 --> 00:01:30,450
Musimy sprawdzić czy do
z lewej strony macierzy lub

29
00:01:30,450 --> 00:01:32,320
Środek tablicy.

30
00:01:32,320 --> 00:01:39,280
Więc tutaj mówimy, jeśli w środku jest wartości
mniejsza niż wartość, oznacza to, że wartość

31
00:01:39,280 --> 00:01:41,350
jest większa niż w połowie
tablicy.

32
00:01:41,350 --> 00:01:45,790
Więc wartość musi być po prawej
element, który po prostu spojrzał na.

33
00:01:45,790 --> 00:01:48,090
>> Więc tutaj, będziemy
szukaj rekurencyjnie.

34
00:01:48,090 --> 00:01:50,320
I będziemy patrzeć na to, co przekazujemy
W tym celu na sekundę.

35
00:01:50,320 --> 00:01:53,440
Ale będziemy szukać do
na prawo od elementu środkowego.

36
00:01:53,440 --> 00:01:57,710
I w drugim przypadku oznacza to, że
wartość była mniejsza niż w połowie

37
00:01:57,710 --> 00:02:00,660
tablicy, i tak będziemy
szukać w lewo.

38
00:02:00,660 --> 00:02:03,520
Teraz lewa będzie
nieco łatwiejsze do zobaczenia.

39
00:02:03,520 --> 00:02:07,770
Tak więc, widzimy, że jesteśmy rekurencyjnie
dzwoniąc wyszukiwanie gdzie pierwszy

40
00:02:07,770 --> 00:02:10,120
argument jest, ponownie, wartość
patrzymy na.

41
00:02:10,120 --> 00:02:14,970
Drugi argument ma być
Tablica szukaliśmy ponad.

42
00:02:14,970 --> 00:02:17,090
I ostatni element jest środkowy.

43
00:02:17,090 --> 00:02:21,650
Zapamiętaj ostatni parametr jest nasz int
n, więc to długość naszej tablicy.

44
00:02:21,650 --> 00:02:25,310
>> W zaproszeniu do wyszukiwania rekurencyjnego jesteśmy
teraz mówi, że długość

45
00:02:25,310 --> 00:02:27,230
Tablica jest środkowy.

46
00:02:27,230 --> 00:02:32,900
Tak więc, jeśli nasza tablica była wielkości 20 i my
Wyszukiwanie w indeksie 10, ponieważ jest środkowa

47
00:02:32,900 --> 00:02:36,930
20 podzielone przez 2, co oznacza, że ​​jesteśmy
przechodząc 10 jako nowe

48
00:02:36,930 --> 00:02:38,300
długość naszej tablicy.

49
00:02:38,300 --> 00:02:41,910
Pamiętaj, że gdy masz tablicę
o długości 10, co oznacza, że ​​ważne

50
00:02:41,910 --> 00:02:45,450
elementy są w indeksach 0 do 9.

51
00:02:45,450 --> 00:02:50,120
Tak, to jest dokładnie to, co chcemy
określić naszą zaktualizowaną tablicę - lewy

52
00:02:50,120 --> 00:02:53,010
tablicy od elementu środkowego.

53
00:02:53,010 --> 00:02:55,710
>> Tak więc, patrząc na prawo jest
nieco trudniejsze.

54
00:02:55,710 --> 00:03:00,170
Teraz pierwsze, rozważmy długość
tablicy z prawej

55
00:03:00,170 --> 00:03:01,240
Element środkowy.

56
00:03:01,240 --> 00:03:08,390
Tak więc, jeśli nasza tablica był wielkości n, to
Nowa tablica będzie rozmiar n minus

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

58
00:03:10,140 --> 00:03:12,530
Więc pomyślmy n minus środku.

59
00:03:12,530 --> 00:03:18,710
>> Ponownie, jeśli tablica miały wielkość 20 i
podzielić przez 2, aby uzyskać środek,

60
00:03:18,710 --> 00:03:23,540
tak środkowy jest 10, to n minus środkowy
ma dać nam 10, więc 10

61
00:03:23,540 --> 00:03:25,330
Elementy z prawej połowie.

62
00:03:25,330 --> 00:03:27,780
Ale mamy też ten minus
1, ponieważ nie chcemy, aby

63
00:03:27,780 --> 00:03:29,700
m.in. samego pola.

64
00:03:29,700 --> 00:03:34,190
Więc n minus środkowa minus 1 daje nam
liczba elementów do prawej

65
00:03:34,190 --> 00:03:36,800
środkowej indeksu tablicy.

66
00:03:36,800 --> 00:03:41,870
>> Teraz tutaj, pamiętaj, że w średnim
parametrem jest tablica wartości.

67
00:03:41,870 --> 00:03:46,180
Więc tutaj, przekazujemy
aktualizowana tablica wartości.

68
00:03:46,180 --> 00:03:50,930
Te wartości dodatnie oraz 1 jest średnim
właściwie mówiąc rekursywnie wywołać

69
00:03:50,930 --> 00:03:56,460
wyszukiwanie, przechodząc w nowej tablicy, gdzie
że nowa tablica zaczyna się w środku

70
00:03:56,460 --> 00:03:59,370
plus jeden z naszych oryginalnych wartości tablicy.

71
00:03:59,370 --> 00:04:05,400
>> Alternatywna składnia, że ​​teraz,
zacząłeś widzieć wskaźniki, jest

72
00:04:05,400 --> 00:04:10,170
Ampersand średnim oraz wartości 1.

73
00:04:10,170 --> 00:04:17,149
Więc chwyć adres środku
plus jeden element wartości.

74
00:04:17,149 --> 00:04:23,690
>> Teraz, jeśli nie były wygodne
modyfikując tablicę takiego, jesteś

75
00:04:23,690 --> 00:04:28,900
mógł również realizowane za pomocą tego
rekurencyjna funkcja pomocnika, gdzie

76
00:04:28,900 --> 00:04:31,680
że funkcja pomocnika trwa
więcej argumentów.

77
00:04:31,680 --> 00:04:36,610
Więc zamiast brać tylko wartość,
tablica i rozmiar tablicy

78
00:04:36,610 --> 00:04:42,315
Funkcja pomocnika może zająć więcej
argumenty, tym niższy wskaźnik

79
00:04:42,315 --> 00:04:45,280
że Ci zależy w tablicy
i górny indeks, który obchodzi

80
00:04:45,280 --> 00:04:46,300
o tablicy.

81
00:04:46,300 --> 00:04:49,770
>> I tak śledzenia zarówno dolna
indeks górny i indeks, nie musisz

82
00:04:49,770 --> 00:04:52,780
trzeba zawsze zmienić
oryginalne wartości tablicy.

83
00:04:52,780 --> 00:04:56,390
Możesz po prostu nadal
korzystać z tablicy wartości.

84
00:04:56,390 --> 00:04:59,540
Ale tutaj zauważyć, że nie potrzebujemy pomocnika
działać tak długo, jak jesteśmy

85
00:04:59,540 --> 00:05:01,760
gotów zmodyfikować oryginalny
Wartości tablicy.

86
00:05:01,760 --> 00:05:05,020
Jesteśmy gotowi przekazać w
zaktualizowanej wartości.

87
00:05:05,020 --> 00:05:09,140
>> Teraz nie możemy binarnego wyszukiwania nad
Tablica jest nieposortowane.

88
00:05:09,140 --> 00:05:12,220
Więc miejmy to załatwione.

89
00:05:12,220 --> 00:05:17,650
Teraz zauważył, że sortowanie jest przeszłość dwa
Parametry int wartości, co jest

90
00:05:17,650 --> 00:05:21,110
Tablica mamy sortowanie i int n,
która jest długością tablicy, która

91
00:05:21,110 --> 00:05:22,250
my sortowania.

92
00:05:22,250 --> 00:05:24,840
Tak, tu chcemy realizować
Algorytm sortowania

93
00:05:24,840 --> 00:05:26,690
że jest o n do kwadratu.

94
00:05:26,690 --> 00:05:30,560
Można wybrać sortowanie bąbelkowe, wybór
sortowania lub wstawiania sortowania, lub

95
00:05:30,560 --> 00:05:32,670
inny rodzaj nie mamy
widoczne w klasie.

96
00:05:32,670 --> 00:05:36,380
Ale tu, będziemy
korzystać wyboru Sortuj.

97
00:05:36,380 --> 00:05:40,030
>> Tak, jedziemy do iteracji
całego układu.

98
00:05:40,030 --> 00:05:44,360
Cóż, tutaj widzimy, że mamy do iteracji
od 0 do n minus 1.

99
00:05:44,360 --> 00:05:45,990
Dlaczego nie wszyscy aż do n?

100
00:05:45,990 --> 00:05:49,320
Cóż, jeśli mamy już posortowane pierwszy
n minus 1, to elementy

101
00:05:49,320 --> 00:05:54,420
Ostatnim elementem tego, co musi być już
w odpowiednim miejscu, tak sortowania na

102
00:05:54,420 --> 00:05:56,520
cała tablica.

103
00:05:56,520 --> 00:05:58,770
>> Teraz pamiętam, jak wybór
sortowania działa.

104
00:05:58,770 --> 00:06:01,950
Zamierzamy przejść całego układu
patrząc na wartości minimalnej

105
00:06:01,950 --> 00:06:04,480
i kij, że tablica
na początku.

106
00:06:04,480 --> 00:06:07,610
Wtedy będziemy iść na całego
tablica znowu patrząc na sekundę

107
00:06:07,610 --> 00:06:10,410
najmniejszy element, i trzymać się, że
na drugiej pozycji w

108
00:06:10,410 --> 00:06:12,100
tablica i tak dalej.

109
00:06:12,100 --> 00:06:14,330
Tak, to co to robi.

110
00:06:14,330 --> 00:06:17,290
>> Tutaj widzimy, że jesteśmy
Ustawienie aktualnego minimum

111
00:06:17,290 --> 00:06:20,030
wartość indeksu i-tego.

112
00:06:20,030 --> 00:06:23,160
Więc w pierwszej iteracji, jedziemy
do rozważenia jest minimalna wartość

113
00:06:23,160 --> 00:06:25,030
Początek naszej tablicy.

114
00:06:25,030 --> 00:06:28,500
Następnie jedziemy do iteracyjnego
Pozostała część układu, w celu sprawdzenia

115
00:06:28,500 --> 00:06:31,870
sprawdzić, czy wszystkie elementy mniejsze niż
jeden, że jesteśmy obecnie

116
00:06:31,870 --> 00:06:33,900
biorąc pod uwagę minimum.

117
00:06:33,900 --> 00:06:38,840
>> Więc tutaj, wartości j plus jeden - to jest
mniej niż to, co mamy obecnie

118
00:06:38,840 --> 00:06:40,380
biorąc pod uwagę minimum.

119
00:06:40,380 --> 00:06:42,940
Wtedy będziemy aktualizować co
uważamy, że jest minimalna

120
00:06:42,940 --> 00:06:44,640
Indeks j oraz 1.

121
00:06:44,640 --> 00:06:48,540
Tak, to, że na całej tablicy,
i po to minimum dla pętli,

122
00:06:48,540 --> 00:06:53,160
powinna być minimalna od elementu
Pozycja I-go w tablicy.

123
00:06:53,160 --> 00:06:57,350
>> Kiedy już mamy, możemy zamienić
Minimalna wartość na i-tej pozycji

124
00:06:57,350 --> 00:06:58,230
w tablicy.

125
00:06:58,230 --> 00:07:00,130
Więc jest to tylko zwykła zamiana.

126
00:07:00,130 --> 00:07:03,940
Przechowujemy w wartości czasowej -
wartość i-tego w tablicy -

127
00:07:03,940 --> 00:07:08,460
umieścić w i-tej wartości w tablicy
Minimalna wartość, jaką należy tam,

128
00:07:08,460 --> 00:07:13,580
, a następnie z powrotem do przechowywania, gdzie
Obecna wartość minimalna dawniej

129
00:07:13,580 --> 00:07:16,460
i-wartość w tablicy, tak
że nie straci go.

130
00:07:16,460 --> 00:07:20,510
>> Tak, że w dalszym ciągu na
kolejnej iteracji.

131
00:07:20,510 --> 00:07:23,480
Zaczniemy patrząc na sekundę
Minimalna wartość i wstawić, że do

132
00:07:23,480 --> 00:07:24,590
druga pozycja.

133
00:07:24,590 --> 00:07:27,440
Na trzeciej iteracji, będziemy szukać
Trzecia wartość minimalna i wkładka

134
00:07:27,440 --> 00:07:31,550
że w trzecim położeniu, a więc
dopóki mamy posortowaną tablicę.

135
00:07:31,550 --> 00:07:33,820
Nazywam się Rob, i to
był wybór sortowania.

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