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

2
00:00:13,300 --> 00:00:15,010
>> ROB Bowden: Hi, saya Rob.

3
00:00:15,010 --> 00:00:16,790
Bagaimana kita menggunakan carian binari?

4
00:00:16,790 --> 00:00:18,770
Mari kita mengetahui.

5
00:00:18,770 --> 00:00:23,400
Jadi, ambil perhatian bahawa carian ini kita akan
untuk melaksanakan secara rekursif.

6
00:00:23,400 --> 00:00:27,470
Anda juga boleh melaksanakan carian binari
iterative, jadi jika anda lakukan itu,

7
00:00:27,470 --> 00:00:29,280
itulah betul-betul halus.

8
00:00:29,280 --> 00:00:32,820
>> Sekarang pertama, mari kita ingat apa yang
parameter untuk carian adalah bertujuan untuk menjadi.

9
00:00:32,820 --> 00:00:36,120
Di sini, kita melihat nilai int, yang merupakan
sepatutnya nilai pengguna adalah

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

11
00:00:37,320 --> 00:00:40,800
Kami melihat pelbagai nilai-nilai int, yang
adalah pelbagai di mana kita

12
00:00:40,800 --> 00:00:42,520
mencari nilai.

13
00:00:42,520 --> 00:00:45,602
Dan kita melihat int n, yang merupakan
panjang pelbagai kami.

14
00:00:45,602 --> 00:00:47,410
>> Sekarang, perkara pertama yang pertama.

15
00:00:47,410 --> 00:00:51,350
Kami menyemak untuk melihat jika n sama dengan 0, dalam
mana kita pulangan palsu.

16
00:00:51,350 --> 00:00:54,770
Itu hanya mengatakan jika kita mempunyai kosong
pelbagai, nilai adalah jelas tidak dalam

17
00:00:54,770 --> 00:00:57,860
array kosong, kita boleh kembali palsu.

18
00:00:57,860 --> 00:01:01,250
>> Sekarang, kita benar-benar mahu melakukan perduaan
carian sebahagian daripada carian binari.

19
00:01:01,250 --> 00:01:04,780
Oleh itu, kami ingin mencari tengah-tengah
elemen array ini.

20
00:01:04,780 --> 00:01:09,130
Di sini, kita katakan pertengahan sama n dibahagikan
sebanyak 2, kerana unsur tengah adalah

21
00:01:09,130 --> 00:01:12,240
akan menjadi panjang
pelbagai kami dibahagikan dengan 2.

22
00:01:12,240 --> 00:01:15,040
Sekarang kita akan memeriksa untuk melihat jika
unsur pertengahan sama nilai kita

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

24
00:01:16,160 --> 00:01:21,030
Jadi, jika nilai-nilai pertengahan sama nilai, kita
boleh kembali benar kerana kami mendapati

25
00:01:21,030 --> 00:01:22,810
nilai dalam pelbagai kami.

26
00:01:22,810 --> 00:01:26,380
>> Tetapi jika itu adalah tidak benar, kini
yang perlu kita lakukan rekursif yang

27
00:01:26,380 --> 00:01:27,840
langkah carian binari.

28
00:01:27,840 --> 00:01:30,450
Kita perlu mencari sama ada kepada
meninggalkan array atau kepada

29
00:01:30,450 --> 00:01:32,320
tengah array.

30
00:01:32,320 --> 00:01:39,280
Jadi di sini, kita katakan jika nilai pada tengah
kurang daripada nilai, ini bermakna nilai yang

31
00:01:39,280 --> 00:01:41,350
adalah lebih besar daripada tengah-tengah
array.

32
00:01:41,350 --> 00:01:45,790
Jadi nilai mesti hak
elemen yang kita hanya memandang.

33
00:01:45,790 --> 00:01:48,090
>> Jadi di sini, kita akan
mencari secara rekursif.

34
00:01:48,090 --> 00:01:50,320
Dan kita akan melihat apa yang kita lulus
ini dalam satu saat.

35
00:01:50,320 --> 00:01:53,440
Tetapi kita akan mencari kepada
hak unsur tengah.

36
00:01:53,440 --> 00:01:57,710
Dan dalam hal yang lain, ini bermakna bahawa
nilai adalah kurang daripada tengah-tengah

37
00:01:57,710 --> 00:02:00,660
pelbagai, dan dengan itu kita akan
untuk mencari ke kiri.

38
00:02:00,660 --> 00:02:03,520
Sekarang, kiri akan menjadi
lebih mudah untuk melihat.

39
00:02:03,520 --> 00:02:07,770
Jadi, kita lihat di sini bahawa kita secara rekursif
memanggil carian mana yang pertama

40
00:02:07,770 --> 00:02:10,120
hujah adalah, sekali lagi, nilai
kami sedang mencari lebih.

41
00:02:10,120 --> 00:02:14,970
Hujah kedua akan menjadi
array yang kita telah mencari lebih.

42
00:02:14,970 --> 00:02:17,090
Dan elemen terakhir sekarang ialah tengah.

43
00:02:17,090 --> 00:02:21,650
Ingat parameter yang terakhir adalah int kami
n, supaya panjang pelbagai kami.

44
00:02:21,650 --> 00:02:25,310
>> Dalam panggilan rekursif untuk mencari, kami
yang mengatakan satu-panjang

45
00:02:25,310 --> 00:02:27,230
array adalah pertengahan.

46
00:02:27,230 --> 00:02:32,900
Jadi, jika pelbagai kami adalah saiz 20 dan kita
searched di indeks 10, sejak tengah

47
00:02:32,900 --> 00:02:36,930
20 dibahagikan dengan 2, ini bermakna kita
lulus 10 sebagai baru

48
00:02:36,930 --> 00:02:38,300
panjang pelbagai kami.

49
00:02:38,300 --> 00:02:41,910
Ingat bahawa apabila anda mempunyai satu pameran
panjang 10, ini bermakna sah

50
00:02:41,910 --> 00:02:45,450
elemen dalam indeks 0 hingga 9.

51
00:02:45,450 --> 00:02:50,120
Jadi ini adalah apa yang kita mahu
nyatakan pelbagai kami dikemaskini - kiri

52
00:02:50,120 --> 00:02:53,010
array dari unsur tengah.

53
00:02:53,010 --> 00:02:55,710
>> Jadi, mencari ke kanan adalah
sedikit lebih sukar.

54
00:02:55,710 --> 00:03:00,170
Sekarang pertama, mari kita pertimbangkan panjang
array ke kanan

55
00:03:00,170 --> 00:03:01,240
elemen tengah.

56
00:03:01,240 --> 00:03:08,390
Jadi, jika pelbagai kami adalah bersaiz n, maka
array baru akan bersaiz n tolak

57
00:03:08,390 --> 00:03:10,140
tolak tengah 1.

58
00:03:10,140 --> 00:03:12,530
Jadi, mari kita memikirkan n tolak tengah.

59
00:03:12,530 --> 00:03:18,710
>> Sekali lagi, jika pelbagai berada di dalam saiz 20 dan
kita bahagikan dengan 2 untuk mendapatkan tengah-tengah,

60
00:03:18,710 --> 00:03:23,540
jadi tengah-tengah adalah 10, maka n tolak pertengahan
akan memberikan kita 10, jadi 10

61
00:03:23,540 --> 00:03:25,330
unsur-unsur di sebelah kanan tengah.

62
00:03:25,330 --> 00:03:27,780
Tetapi kita juga mempunyai tolak ini
1, kerana kita tidak mahu

63
00:03:27,780 --> 00:03:29,700
termasuk pertengahan itu sendiri.

64
00:03:29,700 --> 00:03:34,190
Jadi n tolak kanan tolak 1 memberikan kita
Jumlah unsur ke kanan

65
00:03:34,190 --> 00:03:36,800
indeks tengah dalam array.

66
00:03:36,800 --> 00:03:41,870
>> Sekarang di sini, ingat bahawa tengah-tengah
parameter adalah nilai-nilai yang pelbagai.

67
00:03:41,870 --> 00:03:46,180
Jadi di sini, kami melalui satu
dikemaskini nilai array.

68
00:03:46,180 --> 00:03:50,930
Ini nilai plus plus tengah 1 adalah
sebenarnya mengatakan secara rekursif memanggil

69
00:03:50,930 --> 00:03:56,460
carian, lulus dalam pelbagai baru, di mana
yang pelbagai baru bermula di tengah-tengah

70
00:03:56,460 --> 00:03:59,370
tambah satu nilai-nilai pelbagai asal kami.

71
00:03:59,370 --> 00:04:05,400
>> Satu sintaks ganti untuk itu, sekarang bahawa
anda mula melihat petunjuk, adalah

72
00:04:05,400 --> 00:04:10,170
nilai ditambah Ampersand tengah 1.

73
00:04:10,170 --> 00:04:17,149
Jadi, merebut alamat tengah-tengah
tambah satu elemen nilai-nilai.

74
00:04:17,149 --> 00:04:23,690
>> Sekarang, jika anda tidak selesa
mengubah suai pelbagai seperti itu, anda

75
00:04:23,690 --> 00:04:28,900
boleh juga telah melaksanakan ini menggunakan
fungsi pembantu rekursif, di mana

76
00:04:28,900 --> 00:04:31,680
bahawa fungsi pembantu mengambil
lebih hujah.

77
00:04:31,680 --> 00:04:36,610
Jadi, daripada pengambilan hanya nilai,
pelbagai, dan saiz array,

78
00:04:36,610 --> 00:04:42,315
fungsi pembantu boleh mengambil lebih
hujah, termasuk indeks yang lebih rendah

79
00:04:42,315 --> 00:04:45,280
yang anda mengambil berat tentang dalam tatasusunan
dan indeks atas bahawa anda mengambil berat

80
00:04:45,280 --> 00:04:46,300
mengenai array.

81
00:04:46,300 --> 00:04:49,770
>> Dan sebagainya mengesan kedua-dua yang lebih rendah
indeks dan indeks atas, anda tidak perlu

82
00:04:49,770 --> 00:04:52,780
perlu pernah mengubah suai
nilai-nilai asalnya array.

83
00:04:52,780 --> 00:04:56,390
Anda hanya boleh terus
menggunakan pelbagai nilai-nilai.

84
00:04:56,390 --> 00:04:59,540
Tetapi di sini, notis kita tidak memerlukan seorang pembantu
berfungsi selagi kita

85
00:04:59,540 --> 00:05:01,760
bersedia untuk mengubah suai asal
nilai-nilai pelbagai.

86
00:05:01,760 --> 00:05:05,020
Kami bersedia untuk lulus dalam
satu nilai-nilai dikemaskini.

87
00:05:05,020 --> 00:05:09,140
>> Sekarang, kita tidak boleh carian binari lebih
pelbagai yang Unsorted.

88
00:05:09,140 --> 00:05:12,220
Jadi, mari kita mendapatkan ini diselesaikan.

89
00:05:12,220 --> 00:05:17,650
Sekarang, notis jenis yang lalu dua
parameter int nilai-nilai, yang merupakan

90
00:05:17,650 --> 00:05:21,110
array yang kita menyusun, dan int n,
iaitu panjang array yang

91
00:05:21,110 --> 00:05:22,250
kita sorting.

92
00:05:22,250 --> 00:05:24,840
Jadi, di sini kita ingin melaksanakan
algoritma yang menyusun

93
00:05:24,840 --> 00:05:26,690
yang o n kuasa dua.

94
00:05:26,690 --> 00:05:30,560
Anda boleh memilih jenis gelembung, pemilihan
jenis, atau jenis kemasukan, atau

95
00:05:30,560 --> 00:05:32,670
beberapa jenis lain yang kami tidak mempunyai
dilihat di dalam kelas.

96
00:05:32,670 --> 00:05:36,380
Tetapi di sini, kita akan
menggunakan jenis pemilihan.

97
00:05:36,380 --> 00:05:40,030
>> Jadi, kita akan melelar
atas seluruh array.

98
00:05:40,030 --> 00:05:44,360
Nah, di sini kita lihat bahawa kita iterating
dari 0 hingga n tolak 1.

99
00:05:44,360 --> 00:05:45,990
Mengapa tidak semua jalan sehingga n?

100
00:05:45,990 --> 00:05:49,320
Nah, jika kita sudah disusun pertama
n tolak 1 unsur-unsur, maka

101
00:05:49,320 --> 00:05:54,420
elemen yang terakhir apa yang sudah mesti
di tempat yang betul, jadi menyusun lebih

102
00:05:54,420 --> 00:05:56,520
keseluruhan pelbagai.

103
00:05:56,520 --> 00:05:58,770
>> Sekarang, ingat bagaimana pemilihan
jenis kerja-kerja.

104
00:05:58,770 --> 00:06:01,950
Kami akan pergi ke pelbagai keseluruhan
mencari nilai minimum dalam

105
00:06:01,950 --> 00:06:04,480
array dan kayu yang
pada permulaan.

106
00:06:04,480 --> 00:06:07,610
Kemudian kita akan pergi ke atas keseluruhan
pelbagai lagi mencari kedua

107
00:06:07,610 --> 00:06:10,410
unsur yang paling kecil, dan kayu yang
dalam kedudukan kedua dalam

108
00:06:10,410 --> 00:06:12,100
pelbagai, dan sebagainya.

109
00:06:12,100 --> 00:06:14,330
Jadi, itulah yang ini lakukan.

110
00:06:14,330 --> 00:06:17,290
>> Di sini, kita melihat bahawa kita
menetapkan minimum semasa

111
00:06:17,290 --> 00:06:20,030
nilai kepada indeks i-ke-.

112
00:06:20,030 --> 00:06:23,160
Maka pada lelaran pertama, kita akan
untuk mempertimbangkan nilai minimum untuk

113
00:06:23,160 --> 00:06:25,030
permulaan pelbagai kami.

114
00:06:25,030 --> 00:06:28,500
Kemudian, kita akan melelar sepanjang
selebihnya array, memeriksa untuk

115
00:06:28,500 --> 00:06:31,870
melihat jika terdapat apa-apa unsur-unsur yang lebih kecil daripada
satu yang kita kini

116
00:06:31,870 --> 00:06:33,900
mempertimbangkan minimum.

117
00:06:33,900 --> 00:06:38,840
>> Jadi di sini, menghargai j tambah satu - yang
kurang daripada apa yang kita pada masa ini

118
00:06:38,840 --> 00:06:40,380
mempertimbangkan minimum.

119
00:06:40,380 --> 00:06:42,940
Kemudian kita akan mengemas kini apa
kita fikir adalah minimum untuk

120
00:06:42,940 --> 00:06:44,640
indeks j campur 1.

121
00:06:44,640 --> 00:06:48,540
Jadi, adakah yang di seluruh array,
dan selepas ini untuk gelung, minimum

122
00:06:48,540 --> 00:06:53,160
akan menjadi elemen yang minimum dari
kedudukan ke-i dalam array.

123
00:06:53,160 --> 00:06:57,350
>> Apabila kita mempunyai itu, kita boleh menukar
nilai minimum ke dalam kedudukan i-ke-

124
00:06:57,350 --> 00:06:58,230
dalam array.

125
00:06:58,230 --> 00:07:00,130
Jadi ini adalah hanya swap standard.

126
00:07:00,130 --> 00:07:03,940
Kami menyimpan dalam nilai sementara -
nilai i-ke-dalam tatasusunan -

127
00:07:03,940 --> 00:07:08,460
dimasukkan ke dalam nilai i-ke-dalam tatasusunan yang
nilai minimum yang dimiliki di sana,

128
00:07:08,460 --> 00:07:13,580
dan kemudian menyimpan semula ke dalam mana
nilai minimum semasa digunakan sebagai

129
00:07:13,580 --> 00:07:16,460
i-ke-nilai dalam tatasusunan, jadi
kami tidak hilang.

130
00:07:16,460 --> 00:07:20,510
>> Jadi, yang terus di
lelaran seterusnya.

131
00:07:20,510 --> 00:07:23,480
Kami akan mula mencari yang kedua
nilai minimum dan memasukkan itu ke dalam

132
00:07:23,480 --> 00:07:24,590
kedudukan kedua.

133
00:07:24,590 --> 00:07:27,440
Pada lelaran ketiga, kami akan mencari
nilai minimum ketiga dan memasukkan

134
00:07:27,440 --> 00:07:31,550
itu ke dalam kedudukan ketiga, dan sebagainya
sehingga kita mempunyai pelbagai disusun.

135
00:07:31,550 --> 00:07:33,820
Nama saya Rob, dan ini
adalah jenis pemilihan.

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