>> [MUSIC PLAYING]
>> Doug LLOYD: Baiklah.
Jadi pencarian biner adalah algoritma kita dapat menggunakan
untuk menemukan elemen dalam array.
Tidak seperti pencarian linear, memerlukan kondisi khusus dipenuhi terlebih dahulu,
tapi itu jauh lebih efisien jika bahwa kondisi ini, pada kenyataannya, bertemu.
>> Jadi apa ide di sini?
itu membagi dan menaklukkan.
Kami ingin mengurangi ukuran area pencarian dengan setengah setiap kali
dalam rangka untuk menemukan sejumlah sasaran.
Di sinilah kondisi yang datang ke dalam bermain, meskipun.
Kami hanya dapat memanfaatkan kekuatan menghilangkan setengah dari elemen
bahkan tanpa melihat mereka jika array diurutkan.
>> Jika itu adalah campuran lengkap up, kita tidak bisa hanya keluar dari tangan
membuang setengah dari unsur-unsur, karena kita tidak tahu apa yang kita membuang.
Tetapi jika array diurutkan, kita bisa melakukan itu, karena kita
tahu bahwa segala sesuatu ke kiri di mana kita saat ini adalah
harus lebih rendah dari nilai kita saat ini di.
Dan segala sesuatu ke kanan di mana kita berada
harus lebih besar dari nilai saat ini kami sedang melihat.
>> Jadi apa pseudocode langkah-langkah untuk pencarian biner?
Kami ulangi proses ini sampai array atau, seperti yang kita melanjutkan melalui,
sub array, potongan-potongan kecil array asli, adalah ukuran 0.
Hitung titik tengah sub array saat.
>> Jika nilai yang Anda cari adalah dalam elemen array, berhenti.
Anda menemukannya.
Itu bagus.
Jika tidak, jika target adalah kurang dari apa yang di tengah,
jadi jika nilai yang kita cari untuk lebih rendah dari apa yang kita lihat,
ulangi proses ini lagi, tapi mengubah titik akhir, bukan
menjadi asli menyelesaikan array penuh,
menjadi hanya ke kiri dari mana kita hanya melihat.
>> Kami tahu bahwa tengah itu terlalu tinggi, atau target kurang dari tengah,
dan sehingga harus ada, jika ada sama sekali dalam array,
suatu tempat di sebelah kiri titik tengah.
Dan jadi kita akan mengatur array lokasi hanya ke kiri
dari titik tengah sebagai titik akhir baru.
Sebaliknya, jika target adalah lebih besar dari apa yang di tengah,
kita melakukan yang sama persis proses, tetapi sebaliknya kita
mengubah titik awal untuk menjadi hanya di sebelah kanan dari titik tengah
kita hanya dihitung.
Dan kemudian, kita mulai proses lagi.
>> Mari kita memvisualisasikan ini, OK?
Jadi ada banyak hal yang terjadi dan di sini, tapi inilah sebuah array dari 15 elemen.
Dan kita akan melacak dari banyak lebih banyak barang saat ini.
Jadi dalam pencarian linear, kami hanya peduli tentang target.
Tapi kali ini kami ingin peduli di mana kita
mulai terlihat, di mana kita berhenti mencari,
dan apa titik tengah dari array saat ini.
Jadi di sini kita pergi dengan pencarian biner.
Kami cukup banyak baik untuk pergi, kan?
Aku hanya akan meletakkan di bawah sini satu set indeks.
Ini pada dasarnya hanya elemen apa dari array kita bicarakan.
Dengan pencarian linear, kita peduli, karena kita
perlu tahu berapa banyak elemen kita iterasi,
tapi kami tidak benar-benar peduli apa Unsur ini kami sedang melihat.
Dalam pencarian biner, kita lakukan.
Dan mereka hanya ada sebagai panduan sedikit.
>> Jadi kita bisa mulai, kan?
Nah, tidak cukup.
Ingat apa yang saya katakan tentang pencarian biner?
Kita tidak bisa melakukannya pada Array disortir atau yang lain,
kita tidak menjamin bahwa elemen atau nilai-nilai tertentu yang tidak
tanpa sengaja dibuang ketika kita hanya
memutuskan untuk mengabaikan setengah dari array.
>> Jadi langkah pertama dengan pencarian biner adalah Anda harus memiliki array diurutkan.
Dan Anda dapat menggunakan salah penyortiran algoritma kita bicarakan
untuk mendapatkan Anda untuk posisi itu.
Jadi sekarang, kami berada dalam posisi di mana kita dapat melakukan pencarian biner.
>> Jadi mari kita ulangi proses langkah demi langkah dan menjaga
melacak apa yang terjadi seperti yang kita pergi.
Jadi yang pertama yang perlu kita lakukan adalah menghitung titik tengah dari array saat ini.
Yah, kita akan mengatakan kami, pertama semua, mencari nilai 19.
Kami sedang berusaha untuk menemukan nomor 19.
Unsur pertama ini array terletak pada indeks nol,
dan elemen terakhir ini array terletak pada indeks 14.
Dan jadi kita akan memanggil mereka awal dan akhir.
>> Jadi kita menghitung titik tengah dengan menambahkan 0 ditambah 14 dibagi 2;
titik tengah cukup sederhana.
Dan kita dapat mengatakan bahwa titik tengah sekarang 7.
Jadi adalah 15 apa yang kita cari?
Tidak, itu tidak.
Kami sedang mencari 19.
Tapi kita tahu bahwa 19 adalah lebih besar dari apa yang kami temukan di tengah.
>> Jadi apa yang bisa kita lakukan adalah mengubah titik awal
menjadi hanya di sebelah kanan dari titik tengah, dan ulangi proses lagi.
Dan ketika kita melakukan itu, kita sekarang mengatakan titik awal baru berbagai lokasi 8.
Apa yang kita lakukan secara efektif adalah mengabaikan segala sesuatu di sebelah kiri 15.
Kami telah menghilangkan setengah masalah, dan sekarang,
daripada harus mencari lebih dari 15 elemen dalam array kita,
kita hanya harus mencari lebih dari 7.
Jadi 8 adalah titik awal yang baru.
14 masih titik akhir.
>> Dan sekarang, kami pergi ke ini lagi.
Kami menghitung titik tengah baru.
8 ditambah 14 adalah 22, dibagi dengan 2 adalah 11.
Apakah ini yang kita cari?
Tidak, itu tidak.
Kami sedang mencari nilai yang kurang dari apa yang baru saja kami temukan.
Jadi kita akan mengulangi proses lagi.
Kita akan mengubah titik akhir untuk hanya di sebelah kiri titik tengah.
Jadi titik akhir baru menjadi 10.
Dan sekarang, itulah satu-satunya bagian dari array kita harus memilah-milah.
Jadi kita sekarang telah dieliminasi 12 dari 15 elemen.
Kita tahu bahwa jika 19 ada dalam array, itu
harus ada di suatu tempat antara elemen nomor 8 dan elemen nomor 10.
>> Jadi kita menghitung titik tengah baru lagi.
8 ditambah 10 adalah 18, dibagi dengan 2 adalah 9.
Dan dalam hal ini, lihat, Target di tengah.
Kami menemukan persis apa yang kita cari.
Kita bisa berhenti.
Kami berhasil menyelesaikan pencarian biner.
Baiklah.
Jadi kita tahu algoritma ini bekerja jika target adalah
suatu tempat di dalam array.
Ini bekerja jika algoritma target tidak dalam array?
Nah, mari kita memulainya lagi, dan kali ini,
mari kita lihat untuk elemen 16, yang secara visual kita dapat melihat
tidak ada di mana saja di array.
>> Titik awal lagi 0.
Titik akhir lagi 14.
Mereka adalah indeks pertama dan elemen terakhir dari array lengkap.
Dan kita akan pergi melalui proses kami hanya pergi melalui lagi, mencoba untuk menemukan 16,
meskipun secara visual, kita sudah bisa mengatakan bahwa itu tidak akan berada di sana.
Kami hanya ingin memastikan algoritma ini akan, pada kenyataannya, masih bekerja dalam beberapa cara
dan tidak hanya meninggalkan kita terjebak dalam loop tak terbatas.
>> Jadi apa langkah pertama?
Hitung titik tengah dari array saat ini.
Apa titik tengah dari array saat ini?
Nah, itu 7, kan?
14 ditambah 0 dibagi 2 adalah 7.
Apakah 15 apa yang kita cari?
Tidak.
Itu cukup dekat, tapi kami sedang mencari untuk nilai sedikit lebih besar dari itu.
>> Jadi kita tahu bahwa itu akan menjadi tempat di sebelah kiri 15.
Target tersebut lebih besar dari apa yang ada di titik tengah.
Dan jadi kami menetapkan titik awal baru untuk hanya di sebelah kanan tengah.
Titik tengah saat ini 7, sehingga katakanlah titik awal baru adalah 8.
Dan apa yang kita sudah efektif dilakukan lagi diabaikan
seluruh bagian kiri dari array.
>> Sekarang, kita ulangi memproses sekali lagi.
Menghitung titik tengah baru.
8 ditambah 14 adalah 22, dibagi dengan 2 adalah 11.
Apakah 23 apa yang kita cari?
Sayangnya tidak ada.
Kami sedang mencari nilai yang kurang dari 23.
Dan dalam hal ini, kita akan untuk mengubah titik akhir menjadi hanya
di sebelah kiri titik tengah saat ini.
Titik tengah saat ini 11, dan jadi kita akan mengatur titik akhir baru
untuk waktu berikutnya kita pergi melalui proses ini sampai 10.
>> Sekali lagi, kami pergi melalui proses lagi.
Hitung titik tengah.
8 ditambah 10 dibagi 2 adalah 9.
Apakah 19 apa yang kita cari?
Sayangnya tidak ada.
Kami masih mencari sejumlah kurang dari itu.
Jadi kita akan mengubah titik akhir kali ini menjadi hanya di sebelah kiri titik tengah.
Titik tengah saat ini 9, sehingga titik akhir akan menjadi 8.
Dan sekarang, kita hanya melihat di array elemen tunggal.
>> Apa titik tengah array ini?
Yah, itu dimulai pada 8, itu berakhir pada 8, titik tengah adalah 8.
Adalah bahwa apa yang kita cari?
Apakah kita mencari 17?
Tidak, kami sedang mencari 16.
Jadi jika ada dalam array, itu harus ada di suatu tempat
di sebelah kiri di mana kita saat ini berada.
Jadi apa yang akan kita lakukan?
Yah, kita akan mengatur titik akhir menjadi hanya di sebelah kiri titik tengah saat ini.
Jadi kita akan mengubah titik akhir untuk 7.
Apakah Anda melihat apa yang baru saja terjadi di sini, meskipun?
Carilah di sini sekarang.
>> Mulai sekarang lebih besar dari akhir.
Efektif, kedua ujung dari array kita telah menyeberang,
dan titik awal adalah sekarang setelah titik akhir.
Nah, yang tidak masuk akal, kan?
Jadi sekarang, apa yang dapat kita katakan adalah kita memiliki array sub ukuran 0.
Dan setelah kita mendapatkan untuk titik ini, kita sekarang dapat
menjamin elemen yang 16 tidak ada dalam array,
karena titik awal dan titik akhir telah menyeberang.
Dan sehingga tidak ada.
Sekarang, perhatikan bahwa ini sedikit berbeda dari titik awal dan akhir
titik yang sama.
Jika kita telah melihat untuk 17, itu akan memiliki
berada di array, dan titik awal dan titik akhir yang iterasi terakhir
sebelum titik-titik melintasi, kita akan menemukan 17 ada.
Hanya ketika mereka menyeberangi bahwa kita bisa menjamin bahwa elemen tidak
ada di array.
>> Jadi mari kita banyak lebih sedikit langkah dari pencarian linear.
Dalam skenario terburuk, kami memiliki untuk berpisah daftar elemen n
berulang kali dalam setengah untuk menemukan target, baik karena unsur sasaran
akan berada di suatu tempat di babak divisi, atau tidak ada sama sekali.
Jadi dalam kasus terburuk, kita harus berpisah array-- kau tahu?
Log n kali; kita harus memotong masalah
di setengah jumlah tertentu kali.
Angka itu kali adalah log n.
>> Apa skenario kasus terbaik?
Nah, pertama kalinya kami menghitung titik tengah,
kita menemukan apa yang kita cari.
Dalam semua sebelumnya contoh pada pencarian biner
kami baru saja pergi lebih, jika kita memiliki telah mencari elemen 15,
kita akan menemukan bahwa segera.
Itu di awal.
Itu adalah titik tengah upaya pertama di split
dari divisi dalam pencarian biner.
>> Dan di terburuk kasus, pencarian biner berjalan
di log n, yang jauh lebih baik dari pencarian linear, dalam kasus terburuk.
Dalam kasus terbaik, biner pencarian berjalan omega dari 1.
Jadi pencarian biner adalah banyak lebih baik daripada pencarian linear,
tetapi Anda harus berurusan dengan proses menyortir array terlebih dahulu sebelum Anda bisa
memanfaatkan kekuatan pencarian biner.
>> Aku Doug Lloyd.
Ini adalah CS 50.