>> 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.