ROB Bowden: Hi, aku Rob. Bagaimana kita menggunakan pencarian biner? Mari kita cari tahu. Jadi, perhatikan bahwa pencarian ini kita akan untuk menerapkan rekursif. Anda juga bisa menerapkan pencarian biner iteratif, jadi jika Anda melakukan itu, itu baik-baik saja. 

Sekarang pertama, mari kita ingat apa yang parameter untuk pencarian dimaksudkan untuk menjadi. Di sini, kita melihat nilai int, yang seharusnya nilai pengguna mencari. Kami melihat nilai-nilai int array, yang adalah array di mana kita mencari nilai. Dan kita melihat int n, yang panjang array kami. 

Sekarang, hal pertama yang pertama. Kami memeriksa untuk melihat apakah n sama dengan 0, di hal ini kita kembali palsu. Itu hanya mengatakan jika kita memiliki kosong array, nilai jelas tidak dalam array kosong, sehingga kita dapat kembali palsu. 

Sekarang, kami benar-benar ingin melakukan biner Pencarian bagian dari pencarian biner. Jadi, kita ingin mencari tengah elemen dari array ini. Di sini, kita katakan tengah sama n dibagi oleh 2, karena elemen tengah adalah akan menjadi panjang array kita dibagi 2. Sekarang kita akan memeriksa untuk melihat apakah elemen tengah sama dengan nilai kita mencari. Jadi, jika nilai tengah sama dengan nilai, kita dapat kembali benar karena kami menemukan nilai dalam array kita. 

Tapi kalau itu tidak benar, sekarang kita perlu melakukan rekursif langkah pencarian biner. Kita perlu mencari baik ke kiri dari array atau ke tengah array. Jadi di sini, kita katakan jika nilai-nilai di tengah adalah kurang dari nilai, yang berarti nilai tersebut lebih besar dari tengah dari array. Jadi nilai harus ke kanan elemen yang baru saja kita memandang. 

Jadi di sini, kita akan pencarian rekursif. Dan kita akan melihat apa yang kita lewat ini dalam hitungan detik. Tapi kita akan mencari ke kanan elemen tengah. Dan dalam kasus lain, itu berarti bahwa nilai kurang dari tengah array, dan jadi kita akan untuk mencari ke kiri. Sekarang, kiri akan menjadi sedikit lebih mudah untuk melihat. Jadi, kita lihat di sini bahwa kita rekursif memanggil pencarian di mana yang pertama Argumen ini, sekali lagi, nilai kita melihat dari atas. Argumen kedua akan menjadi array itu kita sedang mencari lebih. Dan elemen terakhir saat ini adalah tengah. Ingat parameter terakhir adalah int kami n, sehingga panjang array kami. 

Dalam panggilan rekursif untuk mencari, kami sekarang mengatakan bahwa panjang array tengah. Jadi, jika array kami adalah ukuran 20 dan kami dicari pada indeks 10, karena tengah adalah 20 dibagi 2, itu berarti kita melewati 10 sebagai new panjang array kita. Ingatlah bahwa ketika Anda memiliki sebuah array panjang 10, yang berarti valid elemen di indeks 0 sampai 9. Jadi ini adalah apa yang kita ingin menentukan array kita diperbarui - kiri Array dari elemen tengah. 

Jadi, melihat ke kanan adalah sedikit lebih sulit. Sekarang pertama, mari kita pertimbangkan panjang dari array ke kanan elemen tengah. Jadi, jika array kami adalah ukuran n, maka array baru akan menjadi ukuran n dikurangi dikurangi tengah 1. Jadi, mari kita memikirkan n dikurangi tengah. 

Sekali lagi, jika array adalah ukuran 20 dan kita membagi dengan 2 untuk mendapatkan tengah, jadi tengah adalah 10, maka n dikurangi tengah akan memberi kita 10, jadi 10 elemen di sebelah kanan tengah. Tapi kita juga harus dikurangi ini 1, karena kita tidak ingin termasuk tengah itu sendiri. Jadi n dikurangi tengah dikurangi 1 memberi kita jumlah elemen ke kanan indeks tengah dalam array. 

Sekarang di sini, ingat bahwa tengah parameter adalah nilai array. Jadi di sini, kami melewati sebuah diperbarui nilai array. Ini ditambah nilai tengah ditambah 1 adalah benar-benar mengatakan rekursif panggilan pencarian, lewat di array baru, di mana bahwa array baru dimulai di tengah ditambah satu dari nilai-nilai asli array kita. 

Sebuah sintaks alternatif untuk itu, sekarang Anda sudah mulai melihat pointer, adalah nilai ampersand tengah ditambah 1. Jadi, ambil alamat tengah ditambah satu unsur nilai-nilai. 

Sekarang, jika Anda tidak nyaman memodifikasi array seperti itu, Anda bisa juga telah menerapkan ini menggunakan fungsi pembantu rekursif, di mana bahwa fungsi pembantu mengambil lebih argumen. Jadi, bukannya mengambil hanya nilai, array, dan ukuran dari array, fungsi helper bisa mengambil lebih argumen, termasuk indeks lebih rendah bahwa Anda akan peduli dalam array dan indeks atas bahwa Anda peduli tentang array. 

Dan melacak kedua lebih rendah indeks dan indeks atas, Anda tidak perlu pernah memodifikasi nilai-nilai asli array. Anda hanya dapat terus menggunakan nilai array. Tapi di sini, perhatikan kita tidak perlu pembantu berfungsi selama kita bersedia untuk memodifikasi asli nilai array. Kami bersedia untuk lulus dalam sebuah nilai diperbarui. 

Sekarang, kita tidak bisa pencarian biner lebih array yang disortir. Jadi, mari kita mendapatkan ini diurutkan keluar. Sekarang, perhatikan jenis yang melewati dua parameter int nilai-nilai, yang merupakan array itu kita menyortir, dan int n, yang merupakan panjang array yang kita penyortiran. Jadi, di sini kita ingin menerapkan algoritma sorting yang o n kuadrat. Anda bisa memilih bubble sort, pemilihan sort, atau insertion sort, atau semacam lain yang kita miliki tidak terlihat di kelas. Tapi di sini, kita akan menggunakan selection sort. 

Jadi, kita akan iterate atas seluruh array. Nah, di sini kita melihat bahwa kita iterasi dari 0 sampai n dikurangi 1. Kenapa tidak semua jalan sampai ke n? Nah, jika kita sudah diurutkan pertama n dikurangi 1 elemen, maka Unsur yang terakhir apa yang harus sudah di tempat yang benar, sehingga pemilahan lebih seluruh array. 

Sekarang, ingat bagaimana seleksi sort bekerja. Kita akan pergi ke seluruh array mencari nilai minimum dalam array dan tongkat yang di awal. Kemudian kita akan pergi ke seluruh yang array yang lagi mencari kedua elemen terkecil, dan tongkat yang di posisi kedua dalam array, dan sebagainya. Jadi, itulah yang ini lakukan. 

Di sini, kita melihat bahwa kita pengaturan arus minimum nilai indeks ke-i. Jadi pada iterasi pertama, kita akan untuk mempertimbangkan nilai minimum yang harus awal array kita. Kemudian, kita akan iterate atas sisa array, memeriksa untuk melihat apakah ada unsur-unsur yang lebih kecil daripada salah satu yang kita saat ini mengingat minimum. 

Jadi di sini, nilai-nilai j ditambah satu - itu kurang dari apa yang kita saat ini mengingat minimum. Kemudian kita akan memperbarui apa kita pikirkan adalah minimum untuk j indeks ditambah 1. Jadi, lakukan itu di seluruh array, dan setelah ini untuk loop, minimum harus menjadi elemen minimum dari posisi ke-i dalam array. 

Setelah kita memiliki itu, kita dapat menukar nilai minimum ke posisi ke-i dalam array. Jadi ini hanya swap standar. Kami menyimpan dalam nilai sementara - nilai ke-i dalam array - dimasukkan ke dalam nilai-i di array tersebut nilai minimum yang dimiliki di sana, dan kemudian menyimpan kembali ke tempat nilai minimum saat ini digunakan untuk menjadi nilai ke-i dalam array, sehingga bahwa kita tidak kehilangan itu. 

Jadi, yang terus di iterasi berikutnya. Kami akan mulai mencari kedua nilai minimum dan masukkan itu ke dalam posisi kedua. Pada iterasi ketiga, kita akan mencari nilai minimum ketiga dan insert itu ke posisi ketiga, dan sebagainya sampai kita memiliki array diurutkan. Nama saya Rob, dan ini adalah selection sort.