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.