>> ROB Bowden: Hi, saya Rob.
Bagaimana kita menggunakan carian binari?
Mari kita mengetahui.
Jadi, ambil perhatian bahawa carian ini kita akan untuk melaksanakan secara rekursif.
Anda juga boleh melaksanakan carian binari iterative, jadi jika anda lakukan itu,
itulah betul-betul halus.
>> Sekarang pertama, mari kita ingat apa yang parameter untuk carian adalah bertujuan untuk menjadi.
Di sini, kita melihat nilai int, yang merupakan sepatutnya nilai pengguna adalah
mencari.
Kami melihat pelbagai nilai-nilai int, yang adalah pelbagai di mana kita
mencari nilai.
Dan kita melihat int n, yang merupakan panjang pelbagai kami.
>> Sekarang, perkara pertama yang pertama.
Kami menyemak untuk melihat jika n sama dengan 0, dalam mana kita pulangan palsu.
Itu hanya mengatakan jika kita mempunyai kosong pelbagai, nilai adalah jelas tidak dalam
array kosong, kita boleh kembali palsu.
>> Sekarang, kita benar-benar mahu melakukan perduaan carian sebahagian daripada carian binari.
Oleh itu, kami ingin mencari tengah-tengah elemen array ini.
Di sini, kita katakan pertengahan sama n dibahagikan sebanyak 2, kerana unsur tengah adalah
akan menjadi panjang pelbagai kami dibahagikan dengan 2.
Sekarang kita akan memeriksa untuk melihat jika unsur pertengahan sama nilai kita
mencari.
Jadi, jika nilai-nilai pertengahan sama nilai, kita boleh kembali benar kerana kami mendapati
nilai dalam pelbagai kami.
>> Tetapi jika itu adalah tidak benar, kini yang perlu kita lakukan rekursif yang
langkah carian binari.
Kita perlu mencari sama ada kepada meninggalkan array atau kepada
tengah array.
Jadi di sini, kita katakan jika nilai pada tengah kurang daripada nilai, ini bermakna nilai yang
adalah lebih besar daripada tengah-tengah array.
Jadi nilai mesti hak elemen yang kita hanya memandang.
>> Jadi di sini, kita akan mencari secara rekursif.
Dan kita akan melihat apa yang kita lulus ini dalam satu saat.
Tetapi kita akan mencari kepada hak unsur tengah.
Dan dalam hal yang lain, ini bermakna bahawa nilai adalah kurang daripada tengah-tengah
pelbagai, dan dengan itu kita akan untuk mencari ke kiri.
Sekarang, kiri akan menjadi lebih mudah untuk melihat.
Jadi, kita lihat di sini bahawa kita secara rekursif memanggil carian mana yang pertama
hujah adalah, sekali lagi, nilai kami sedang mencari lebih.
Hujah kedua akan menjadi array yang kita telah mencari lebih.
Dan elemen terakhir sekarang ialah tengah.
Ingat parameter yang terakhir adalah int kami n, supaya panjang pelbagai kami.
>> Dalam panggilan rekursif untuk mencari, kami yang mengatakan satu-panjang
array adalah pertengahan.
Jadi, jika pelbagai kami adalah saiz 20 dan kita searched di indeks 10, sejak tengah
20 dibahagikan dengan 2, ini bermakna kita lulus 10 sebagai baru
panjang pelbagai kami.
Ingat bahawa apabila anda mempunyai satu pameran panjang 10, ini bermakna sah
elemen dalam indeks 0 hingga 9.
Jadi ini adalah apa yang kita mahu nyatakan pelbagai kami dikemaskini - kiri
array dari unsur tengah.
>> Jadi, mencari ke kanan adalah sedikit lebih sukar.
Sekarang pertama, mari kita pertimbangkan panjang array ke kanan
elemen tengah.
Jadi, jika pelbagai kami adalah bersaiz n, maka array baru akan bersaiz n tolak
tolak tengah 1.
Jadi, mari kita memikirkan n tolak tengah.
>> Sekali lagi, jika pelbagai berada di dalam saiz 20 dan kita bahagikan dengan 2 untuk mendapatkan tengah-tengah,
jadi tengah-tengah adalah 10, maka n tolak pertengahan akan memberikan kita 10, jadi 10
unsur-unsur di sebelah kanan tengah.
Tetapi kita juga mempunyai tolak ini 1, kerana kita tidak mahu
termasuk pertengahan itu sendiri.
Jadi n tolak kanan tolak 1 memberikan kita Jumlah unsur ke kanan
indeks tengah dalam array.
>> Sekarang di sini, ingat bahawa tengah-tengah parameter adalah nilai-nilai yang pelbagai.
Jadi di sini, kami melalui satu dikemaskini nilai array.
Ini nilai plus plus tengah 1 adalah sebenarnya mengatakan secara rekursif memanggil
carian, lulus dalam pelbagai baru, di mana yang pelbagai baru bermula di tengah-tengah
tambah satu nilai-nilai pelbagai asal kami.
>> Satu sintaks ganti untuk itu, sekarang bahawa anda mula melihat petunjuk, adalah
nilai ditambah Ampersand tengah 1.
Jadi, merebut alamat tengah-tengah tambah satu elemen nilai-nilai.
>> Sekarang, jika anda tidak selesa mengubah suai pelbagai seperti itu, anda
boleh juga telah melaksanakan ini menggunakan fungsi pembantu rekursif, di mana
bahawa fungsi pembantu mengambil lebih hujah.
Jadi, daripada pengambilan hanya nilai, pelbagai, dan saiz array,
fungsi pembantu boleh mengambil lebih hujah, termasuk indeks yang lebih rendah
yang anda mengambil berat tentang dalam tatasusunan dan indeks atas bahawa anda mengambil berat
mengenai array.
>> Dan sebagainya mengesan kedua-dua yang lebih rendah indeks dan indeks atas, anda tidak perlu
perlu pernah mengubah suai nilai-nilai asalnya array.
Anda hanya boleh terus menggunakan pelbagai nilai-nilai.
Tetapi di sini, notis kita tidak memerlukan seorang pembantu berfungsi selagi kita
bersedia untuk mengubah suai asal nilai-nilai pelbagai.
Kami bersedia untuk lulus dalam satu nilai-nilai dikemaskini.
>> Sekarang, kita tidak boleh carian binari lebih pelbagai yang Unsorted.
Jadi, mari kita mendapatkan ini diselesaikan.
Sekarang, notis jenis yang lalu dua parameter int nilai-nilai, yang merupakan
array yang kita menyusun, dan int n, iaitu panjang array yang
kita sorting.
Jadi, di sini kita ingin melaksanakan algoritma yang menyusun
yang o n kuasa dua.
Anda boleh memilih jenis gelembung, pemilihan jenis, atau jenis kemasukan, atau
beberapa jenis lain yang kami tidak mempunyai dilihat di dalam kelas.
Tetapi di sini, kita akan menggunakan jenis pemilihan.
>> Jadi, kita akan melelar atas seluruh array.
Nah, di sini kita lihat bahawa kita iterating dari 0 hingga n tolak 1.
Mengapa tidak semua jalan sehingga n?
Nah, jika kita sudah disusun pertama n tolak 1 unsur-unsur, maka
elemen yang terakhir apa yang sudah mesti di tempat yang betul, jadi menyusun lebih
keseluruhan pelbagai.
>> Sekarang, ingat bagaimana pemilihan jenis kerja-kerja.
Kami akan pergi ke pelbagai keseluruhan mencari nilai minimum dalam
array dan kayu yang pada permulaan.
Kemudian kita akan pergi ke atas keseluruhan pelbagai lagi mencari kedua
unsur yang paling kecil, dan kayu yang dalam kedudukan kedua dalam
pelbagai, dan sebagainya.
Jadi, itulah yang ini lakukan.
>> Di sini, kita melihat bahawa kita menetapkan minimum semasa
nilai kepada indeks i-ke-.
Maka pada lelaran pertama, kita akan untuk mempertimbangkan nilai minimum untuk
permulaan pelbagai kami.
Kemudian, kita akan melelar sepanjang selebihnya array, memeriksa untuk
melihat jika terdapat apa-apa unsur-unsur yang lebih kecil daripada satu yang kita kini
mempertimbangkan minimum.
>> Jadi di sini, menghargai j tambah satu - yang kurang daripada apa yang kita pada masa ini
mempertimbangkan minimum.
Kemudian kita akan mengemas kini apa kita fikir adalah minimum untuk
indeks j campur 1.
Jadi, adakah yang di seluruh array, dan selepas ini untuk gelung, minimum
akan menjadi elemen yang minimum dari kedudukan ke-i dalam array.
>> Apabila kita mempunyai itu, kita boleh menukar nilai minimum ke dalam kedudukan i-ke-
dalam array.
Jadi ini adalah hanya swap standard.
Kami menyimpan dalam nilai sementara - nilai i-ke-dalam tatasusunan -
dimasukkan ke dalam nilai i-ke-dalam tatasusunan yang nilai minimum yang dimiliki di sana,
dan kemudian menyimpan semula ke dalam mana nilai minimum semasa digunakan sebagai
i-ke-nilai dalam tatasusunan, jadi kami tidak hilang.
>> Jadi, yang terus di lelaran seterusnya.
Kami akan mula mencari yang kedua nilai minimum dan memasukkan itu ke dalam
kedudukan kedua.
Pada lelaran ketiga, kami akan mencari nilai minimum ketiga dan memasukkan
itu ke dalam kedudukan ketiga, dan sebagainya sehingga kita mempunyai pelbagai disusun.
Nama saya Rob, dan ini adalah jenis pemilihan.