Selasa, 10 Mei 2011

Algoritma Binary Search

Algoritma Binary Search


Jika kita mempunyai sebuah file dari record-record yang telah dijalankan, kita dapat melanjutkan menghapuskan memory pemeriksaan yang diperlukan untuk mendapatkan kembali sebuah record yang telah dipakai oleh suatu teknik binary search. Suatu binary search dibandingkan dengan kunci dari pencarian record dengan record tengah dari sebuah file. Kemudian masing-masing pencarian record yang telah ditempatkan atau setengah dari file yang telah dihilangkan dengan pertimbangan yang lebih lanjut. Dalam kasus yang sebelumnya, proses pembandingan dari record tengah dilanjutkan dalam record-record selanjutnya. Jika kita harus menghilangkan bagian atas dari sebuah file termasuk record yang telah dibandingkan berlawanan. Selanjutnya jika kita harus menghilangkan bagian bawah dari sebuah file termasuk record yang telah dibandingkan berlawanan. Dalam pengulangan proses dari pembandingan berlawanan dari record tengah, kita akhirnya akan menempatkan record yang kita inginkan atau menentukan bahwa itu tidak ada dalam file ketika tidak ada record-record selanjutnya.

Pencarian Biner (Binary Search) dilakukan untuk :
1. memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.
2. Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).
3. Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.

Menemukan nilai dalam urutan diurutkan
Dalam bentuk yang paling sederhana, pencarian biner digunakan untuk cepat menemukan nilai dalam urutan diurutkan (pertimbangkan berurutan array biasa untuk sekarang). Kami akan menelepon nilai mencari nilai target untuk kejelasan. pencarian biner mempertahankan subsequence berdekatan dari urutan mulai dimana nilai target pasti berada. Ini disebut ruang pencarian. Ruang pencarian awalnya adalah seluruh urutan. Pada setiap langkah, algoritma membandingkan nilai rata-rata di ruang pencarian dengan nilai target. Berdasarkan perbandingan dan karena urutan diurutkan, kemudian dapat menghilangkan setengah dari ruang pencarian. Dengan melakukan ini berulang kali, akhirnya akan ditinggalkan dengan ruang pencarian yang terdiri dari elemen tunggal, nilai target.

Sebagai contoh, perhatikan urutan berikut bilangan bulat diurutkan dalam urutan dan mengatakan kami sedang mencari nomor 55:
0 5 13 19 22 41 55 68 72 81 98



Kami tertarik pada lokasi nilai target dalam urutan jadi kita akan mewakili ruang pencarian sebagai indeks ke dalam urutan. Awalnya, ruang pencarian berisi indeks 1 sampai 11. Karena ruang pencarian benar-benar interval, itu hanya cukup untuk menyimpan dua nomor, indeks rendah dan tinggi. Seperti dijelaskan di atas, kita sekarang memilih nilai tengah, yang adalah nilai pada indeks 6 (titik tengah antara 1 dan 11): nilai ini adalah 41 dan itu lebih kecil dari nilai target. Dari ini kita tidak hanya menyimpulkan bahwa elemen pada indeks 6 bukanlah nilai target, tetapi juga bahwa tidak ada elemen pada indeks antara 1 dan 5 bisa menjadi nilai target, karena semua elemen di indeks ini lebih kecil dari 41, yang lebih kecil dari nilai target. Hal ini membawa ruang pencarian ke indeks 7 sampai 11:
55 68 72 81 98



Berjalan dengan cara yang sama, kita memotong paruh kedua ruang pencarian dan yang tersisa dengan:
55 68



Tergantung pada bagaimana kita memilih median bahkan jumlah elemen kami baik akan menemukan 55 pada langkah berikutnya atau memenggal 68 untuk mendapatkan ruang pencarian hanya satu elemen. Either way, kita menyimpulkan bahwa indeks dimana nilai target terletak adalah 7.

Jika nilai target tidak hadir dalam urutan, pencarian biner akan mengosongkan ruang pencarian seluruhnya. Kondisi ini mudah untuk memeriksa dan menangani. Berikut adalah beberapa kode untuk pergi dengan deskripsi:
binary_search (A, target): lo = 1, hi = size (A) sedangkan lo <= hi: pertengahan = lo + (hi-lo) / 2 jika A target == [pertengahan]: kembali pertengahan lain jika A pertengahan [ ] y x. Properti ini adalah apa yang kita gunakan ketika kita membuang paruh kedua ruang pencarian. Hal ini setara dengan mengatakan bahwa p ¬ (x) menyiratkan ¬ p (y) untuk semua y x atau bahwa ¬ p (x) menyiratkan ¬ p (y) untuk semua
Ketika domain predikat adalah bilangan bulat, itu sudah cukup untuk membuktikan bahwa p (x) menyiratkan p (x +1) atau yang p ¬ (x) menyiratkan ¬ p (x-1), sisanya kemudian diikuti dengan induksi.

Kedua bagian yang paling sering interleaved: ketika kita berpikir masalah bisa diselesaikan dengan pencarian biner, kami bertujuan untuk merancang predikat sehingga memenuhi kondisi dalam teorema utama.

Orang mungkin bertanya-tanya mengapa kita memilih untuk menggunakan abstraksi ini daripada algoritma sederhana yang tampak kami telah digunakan sejauh ini. Hal ini karena banyak masalah tidak dapat dimodelkan sebagai mencari nilai tertentu, tetapi mungkin untuk mendefinisikan dan mengevaluasi predikat seperti "Apakah ada tugas yang biaya x atau kurang?", Ketika kita sedang mencari beberapa jenis penugasan dengan biaya terendah. Misalnya, masalah perjalanan salesman biasa (TSP) terlihat untuk perjalanan putaran termurah yang dilihat setiap kota tepat satu kali. Di sini, nilai target tidak didefinisikan seperti itu, tapi kita dapat mendefinisikan sebuah predikat "Apakah ada pulang-pergi yang biaya x atau kurang?" Dan kemudian menerapkan pencarian biner untuk menemukan terkecil x yang memenuhi predikat. Ini disebut mengurangi masalah asli untuk suatu keputusan (ya / tidak) masalah. Sayangnya, kita tahu tidak ada cara efisien mengevaluasi ini predikat tertentu dan sehingga masalah TSP tidak mudah diselesaikan dengan pencarian biner, tapi masalah optimasi banyak.

Mari kita sekarang mengkonversi biner pencarian sederhana pada array diurutkan diuraikan dalam pendahuluan ini definisi abstrak. Pertama, mari kita rephrase masalah sebagai: "A array dan target, nilai return indeks yang pertama dalam elemen A sama dengan atau lebih besar dari target. Nilai Mengingat" Kebetulan, ini lebih atau kurang bagaimana lower_bound berperilaku di C + +.

Kami ingin mencari index dari nilai target, sehingga setiap indeks ke array adalah solusi kandidat. Pencarian ruang S adalah himpunan semua solusi calon, sehingga interval yang mengandung semua indeks. Pertimbangkan predikat "Apakah A [x] lebih besar dari atau sama dengan nilai target?". Jika kita adalah untuk menemukan yang pertama x yang predikatnya kata ya, kita akan mendapatkan apa yang memutuskan kami cari di paragraf sebelumnya.

Kondisi dalam teorema utama puas karena array diurutkan dalam urutan menaik: jika A [x] lebih besar dari atau sama dengan nilai target, semua elemen setelah itu yang pasti juga lebih besar dari atau sama dengan nilai target.

Jika kita mengambil urutan sampel dari sebelumnya:
0 5 13 19 22 41 55 68 72 81 98



Dengan ruang pencarian (indeks):
1 2 3 4 5 6 7 8 9 10 11



Dan menerapkan predikat kami (dengan nilai target 55) untuk itu kita mendapatkan:
tidak ada tidak ada tidak ada tidak ada tidak ada tidak ada ya ya ya ya ya



Ini merupakan rangkaian ada jawaban yang diikuti oleh serangkaian jawaban ya, karena kami mengharapkan. Perhatikan bagaimana indeks 7 (dimana nilai target terletak) adalah pertama yang menghasilkan predikat ya, jadi ini adalah apa pencarian biner kita akan menemukan.

Melaksanakan algoritma diskrit
Satu hal penting yang perlu diingat sebelum mulai kode untuk menetap pada apa dua angka Anda menjaga (batas bawah dan atas) berarti. Jawaban mungkin adalah suatu interval tertutup yang pasti berisi pertama x yang p (x) benar. Semua kode Anda kemudian harus diarahkan untuk mempertahankan invarian ini: ia memberitahu Anda bagaimana benar memindahkan batas, yang merupakan tempat bug dapat dengan mudah menemukan jalan dalam kode Anda, jika Anda tidak hati-hati.

Hal lain yang harus berhati-hati dengan adalah bagaimana tinggi untuk mengatur batas. Dengan "tinggi" Saya benar-benar berarti "lebar" karena ada dua batas perlu khawatir. Setiap sehingga sering terjadi bahwa programmer menyimpulkan selama coding bahwa batas-batas ia mengatur yang cukup luas, hanya untuk menemukan-balik selama istirahat (ketika itu sudah terlambat). Sayangnya, sedikit membantu saran dapat diberikan di sini selain untuk selalu double dan triple-memeriksa batasan Anda! Juga, karena waktu eksekusi meningkat logaritmis dengan batas-batas, Anda selalu dapat mengatur mereka lebih tinggi, asalkan tidak melanggar evaluasi predikat. Jauhkan mata Anda keluar untuk kesalahan overflow di sekitar, terutama dalam menghitung median.

Sekarang kita akhirnya sampai ke kode yang mengimplementasikan pencarian biner seperti yang dijelaskan dalam hal ini dan bagian sebelumnya:
binary_search (lo, hi, p):
sedangkan pertengahan = + lo (hi-lo) / 2
jika p (pertengahan) == benar:
hi = pertengahan
lain:
lo = mid +1

jika p (lo) == false:
mengeluh / / p (x) adalah salah untuk semua x dalam S!

kembali lo / / lo adalah yang paling x yang p (x) benar
Dua garis penting yang hi = mid dan lo = mid +1. Ketika p (pertengahan) benar, kita dapat membuang paruh kedua ruang pencarian, karena predikat tersebut benar untuk semua elemen di dalamnya (oleh teorema utama). Namun, kita tidak bisa membuang pertengahan sendiri, karena mungkin menjadi elemen pertama yang p benar. Inilah sebabnya mengapa memindahkan batas atas hingga pertengahan adalah sebagai agresif bisa kita lakukan tanpa memperkenalkan bug.

Dalam nada yang sama, jika p (pertengahan) adalah palsu, kita dapat membuang paruh pertama ruang pencarian, tapi kali ini termasuk pertengahan. P (pertengahan) adalah salah sehingga kita tidak perlu di ruang pencarian kami. Hal ini secara efektif berarti kita dapat memindahkan batas bawah hingga pertengahan +1.

Jika kita ingin menemukan terakhir x yang p (x) adalah palsu, kami akan merancang (menggunakan alasan yang sama seperti di atas) sesuatu seperti:
/ / Peringatan: ada bug jahat dalam potongan ini!
binary_search (lo, hi, p):
sedangkan pertengahan = lo + (hi-lo) / 2 / / catatan: divisi memotong
jika p (pertengahan) == benar:
hi = pertengahan 1
lain:
lo = pertengahan

jika p (lo) == benar:
mengeluh / / p (x) benar untuk semua x dalam S!

kembali lo / / lo adalah yang terbesar x p (x) adalah palsu
Anda dapat memverifikasi bahwa ini memenuhi kondisi kami bahwa unsur kita cari selalu hadir dalam interval (lo, hi). Namun, ada masalah lain. Pertimbangkan apa yang terjadi ketika Anda menjalankan kode ini pada beberapa ruang pencarian yang memberi predikat:
tidak ada ya
Kode akan terjebak dalam satu lingkaran. Selalu akan memilih elemen pertama sebagai pertengahan, tetapi kemudian tidak akan memindahkan batas bawah karena ingin menjaga pencari ruang di no. Solusinya adalah mengubah pertengahan = lo + (hi-lo) / 2 sampai pertengahan = lo + (hi-lo +1) / 2, yaitu sehingga putaran Facebook bukannya turun. Ada cara lain untuk mendapatkan sekitar masalah, tetapi yang satu ini mungkin merupakan terbersih. Tapi ingatlah untuk selalu menguji kode Anda pada-elemen dua set mana predikat salah untuk elemen pertama dan benar untuk yang kedua.

Anda juga mungkin bertanya-tanya seperti mengapa pertengahan dihitung menggunakan pertengahan = lo + (hi-lo) / 2 bukannya pertengahan biasa = (lo + hi) / 2. Hal ini untuk menghindari bug lain pembulatan potensial: dalam kasus pertama, kita ingin divisi untuk selalu putaran bawah, menuju batas bawah. Tapi divisi memotong, jadi ketika lo + hi akan negatif, hal itu akan mulai pembulatan ke arah yang lebih tinggi terikat. Coding perhitungan cara ini memastikan bahwa jumlah dibagi selalu positif dan karenanya selalu babak seperti yang kita inginkan. Meskipun bug tersebut tidak muncul ketika ruang pencarian hanya terdiri dari bilangan bulat positif atau bilangan real, saya telah memutuskan untuk kode dengan cara ini seluruh artikel untuk konsistensi.

Real nomor
pencarian biner juga dapat digunakan pada fungsi monoton yang domain adalah himpunan bilangan real. Melaksanakan pencarian biner pada real biasanya lebih mudah dari pada bilangan bulat, karena Anda tidak perlu diwaspadai bagaimana cara memindahkan batas:
binary_search (lo, hi, p):
sementara kita memilih untuk tidak berakhir:
pertengahan = + lo (hi-lo) / 2
jika p (pertengahan) == benar:
hi = pertengahan
lain:
lo = pertengahan

kembali lo / / lo dekat dengan perbatasan antara tidak dan ya
Karena himpunan bilangan real yang padat, harus jelas bahwa kita biasanya tidak akan dapat menemukan nilai target yang tepat. Namun, kita dengan cepat dapat menemukan beberapa x sedemikian sehingga f (x) adalah dalam beberapa toleransi perbatasan antara tidak dan ya. Kami memiliki dua cara untuk memutuskan kapan untuk mengakhiri: berakhir pada saat ruang pencarian semakin kecil dari beberapa yang telah ditentukan terikat (katakanlah 10 -12) atau melakukan sejumlah tetap iterasi. Pada TopCoder, Anda terbaik adalah dengan hanya menggunakan beberapa ratus iterasi, ini akan memberikan presisi terbaik tanpa berpikir terlalu banyak. 100 iterasi akan mengurangi ruang pencarian untuk sekitar 10 -30 dari ukuran awal, yang harus cukup untuk sebagian besar (jika tidak semua) masalah.

Jika Anda perlu lakukan sebagai sedikit iterasi mungkin, Anda dapat berakhir pada saat interval semakin kecil, tetapi cobalah untuk melakukan perbandingan relatif dari batas, bukan hanya salah satu yang mutlak. Alasan untuk ini adalah bahwa menggandakan pernah dapat memberikan Anda lebih dari 15 digit desimal presisi jadi jika ruang pencarian mengandung jumlah besar (katakan pada urutan miliar), Anda tidak pernah mendapatkan perbedaan mutlak kurang dari 10 -7.

Contoh
Pada titik ini saya akan menunjukkan bagaimana semua pembicaraan ini dapat digunakan untuk memecahkan masalah TopCoder. Untuk ini saya telah memilih masalah agak sulit, FairWorkload , yang merupakan divisi 1 tingkat 2 masalah dalam SRM 169.

Dalam masalah ini, sejumlah pekerja harus memeriksa sejumlah lemari arsip. Lemari tidak semua ukuran yang sama dan kita diberitahu untuk setiap kabinet berapa banyak folder di dalamnya. Kita diminta untuk mencari tugas sehingga setiap pekerja mendapat serangkaian berurutan kabinet harus melalui dan bahwa hal itu meminimalkan jumlah maksimum folder yang seorang pekerja harus melihat melalui.

Setelah mendapatkan akrab dengan masalah, sentuhan kreativitas diperlukan. Bayangkan bahwa kita memiliki jumlah yang tidak terbatas pekerja di pembuangan kami. Pengamatan penting adalah bahwa, untuk beberapa MAX nomor, kita dapat menghitung jumlah minimum pekerja diperlukan sehingga setiap pekerja harus memeriksa tidak lebih dari folder MAX (jika ini mungkin). Mari kita lihat bagaimana kita akan melakukannya. Beberapa pekerja perlu memeriksa kabinet pertama sehingga kami menetapkan pekerja apapun untuk itu. Namun, karena kabinet harus ditugaskan dalam urutan (pekerja tidak dapat memeriksa lemari 1 dan 3 tanpa memeriksa 2 juga), selalu optimal untuk menugaskannya untuk kabinet kedua juga, jika ini tidak membawanya ke atas batas kita memperkenalkan (MAX). Jika itu akan membawanya ke atas batas, kami menyimpulkan bahwa karyanya dilakukan dan menetapkan seorang pekerja baru ke kabinet kedua. Kami melanjutkan dengan cara yang sama sampai semua lemari telah ditetapkan dan menegaskan bahwa kita telah menggunakan jumlah minimum pekerja mungkin, dengan batas buatan kami memperkenalkan. Perhatikan di sini bahwa jumlah pekerja berbanding terbalik dengan MAX: semakin tinggi kita menetapkan batas kami, para pekerja lebih sedikit kita akan membutuhkan.

Sekarang, jika Anda pergi kembali dan hati-hati memeriksa apa yang kita minta dalam pernyataan masalah, Anda dapat melihat bahwa kita benar-benar diminta untuk MAX terkecil sehingga jumlah pekerja yang dibutuhkan adalah kurang dari atau sama dengan jumlah tenaga kerja yang tersedia . Dengan itu dalam pikiran, kita hampir selesai, kita hanya perlu menghubungkan titik-titik dan melihat bagaimana semua ini cocok dalam frame kita diletakkan untuk memecahkan masalah menggunakan pencarian biner.

Dengan masalah diulang sesuai dengan kebutuhan kita lebih baik, sekarang kita dapat memeriksa predikat Dapat menyebar beban kerja sehingga setiap pekerja harus memeriksa tidak lebih dari x folder, dengan jumlah tenaga kerja yang tersedia terbatas? Kita dapat menggunakan algoritma serakah digambarkan efisien mengevaluasi predikat untuk setiap x. Hal ini menyimpulkan bagian pertama dari membangun solusi pencarian biner, sekarang kita hanya perlu membuktikan bahwa kondisi dalam teorema utama puas. Tapi amati bahwa peningkatan x sebenarnya melemaskan batas pada beban kerja maksimal, sehingga kita hanya bisa memerlukan nomor yang sama pekerja atau kurang, tidak lebih. Jadi, jika predikat mengatakan ya untuk beberapa x, juga akan mengatakan ya untuk semua yang lebih besar x.

Untuk jelasnya, berikut adalah potongan STL-driven yang memecahkan masalah:
int getMostWork (vektor folder, pekerja int) {
int n = folders.size ();
int lo = * max_element (folders.begin (), folders.end ());
int hi = menumpuk (folders.begin (), folders.end (), 0);

while (lo int x = lo + (hi-lo) / 2;

int diperlukan current_load = 1, = 0;
for (int i = 0; i if (current_load + folder [i] <= x) {
/ / Pekerja saat ini dapat mengatasinya
current_load + = folder [i];
}
else {
/ / Menetapkan pekerja berikutnya
+ + Diperlukan;
current_load = map [i];
}
}

jika ( hi = x;
lain
lo = x +1;
}

kembali lo;
}
Perhatikan batas bawah dan atas dengan hati-hati dipilih: Anda bisa mengganti atas terikat dengan integer cukup besar, tetapi batas bawah tidak boleh kurang dari kabinet terbesar untuk menghindari situasi di mana sebuah lemari tunggal akan terlalu besar bagi pekerja apapun, kasus yang tidak akan benar ditangani oleh predikat. Alternatif akan mengatur batas bawah nol, kemudian menangani terlalu kecil x sebagai kasus khusus dalam predikat.

Untuk memverifikasi bahwa solusi tidak mengunci, saya menggunakan tidak kecil / ya misalnya dengan folder = {1,1} dan pekerja = 1.

Kompleksitas keseluruhan dari solusi adalah O (n log SIZE), dimana SIZE adalah ukuran ruang pencarian. Ini sangat cepat.

Seperti yang Anda lihat, kami menggunakan algoritma greedy untuk mengevaluasi predikat. Dalam masalah lain, mengevaluasi predikat bisa turun ke apapun dari ekspresi matematika sederhana untuk mencari pencocokan kardinalitas maksimum pada graf bipart.