Biner cari - salah satu cara termudah untuk menemukan elemen dalam array

Cukup sering, programmer, bahkan pemula, dihadapkan dengan fakta bahwa ada satu set angka, yang harus menemukan nomor tertentu. Ini adalah koleksi ini disebut array. Dan untuk menemukan item di dalamnya, ada segudang cara. Tetapi sederhana kebanyakan dari mereka dapat dianggap pencarian biner di sebelah kanan. Apa metode ini adalah? Dan bagaimana menerapkan pencarian biner? Pascal adalah lingkungan yang paling mudah untuk organisasi dari program seperti itu, jadi kita akan menggunakannya untuk belajar.

Pertama, menganalisis, apa keuntungan dari metode ini, sehingga kita bisa mengerti, apa gunanya dalam studi topik. Jadi, mari kita memiliki sebuah array dengan dimensi setidaknya 100000000 elemen, yang perlu menemukan beberapa. Tentu saja, masalah ini dapat dengan mudah dipecahkan dengan pencarian linear sederhana, di mana kita menggunakan siklus akan membandingkan elemen yang diperlukan dengan semua orang-orang yang dalam array. Masalahnya adalah bahwa pelaksanaan ide ini akan mengambil terlalu banyak waktu. Dalam program Pascal sederhana menjadi beberapa perawatan, dan tiga baris teks utama, Anda tidak akan melihat hal itu, tetapi ketika kita datang ke kurang lebih besar proyek-proyek dengan sejumlah besar cabang dan fungsi yang baik, program ini akan siap untuk dimuat terlalu lama. Apalagi jika komputer adalah kinerja yang lemah. Oleh karena itu, ada pencarian biner, yang mengurangi waktu pencarian setidaknya dua kali.

Jadi, apa prinsip kerja metode ini? Segera harus mengatakan bahwa pencarian biner bekerja tidak dalam array, tapi hanya pada satu set diurutkan dari angka. Pada setiap langkah yang diambil elemen tengah array (artinya jumlah elemen). Jika diperlukan jumlah lebih besar dari rata-rata, maka semua yang tersisa, yang kurang dari sel rata-rata, bisa dibuang dan tidak melihat ada. Sebaliknya, jika kurang dari rata-rata - antara angka-angka ke kanan, Anda tidak bisa mencari. Kemudian pilih area pencarian baru, di mana elemen pertama akan menjadi elemen tengah seluruh array, dan yang terakhir dan kehendak terakhir. Rata-rata jumlah bidang baru akan ¼ dari semua segmen, yaitu, (elemen terakhir + elemen tengah seluruh array) / 2. Sekali lagi, operasi yang sama dilakukan - perbandingan dengan rata-rata jumlah array. Jika nilai target kurang dari rata-rata, kita menolak sisi kanan, dan juga harus dilakukan selanjutnya, sampai sekarang elemen tengah ini tidak akan diinginkan.

Tentu saja, yang terbaik adalah untuk melihat contoh bagaimana menulis pencarian biner. Pascal sini akan sesuai dengan siapa pun - versi tidak penting. Mari kita menulis sebuah program yang sederhana.

Ini adalah sebuah array dari 1 sampai h di bawah nama "massiv", variabel yang menunjukkan batas bawah dari pencarian, yang disebut "Niz", batas atas, yang disebut "verh", rata-rata pencarian istilah - "sredn"; dan jumlah yang diperlukan - "isiko".

Jadi, pertama kita menetapkan batas atas dan bawah dari pencarian kisaran:

Niz: = 1;
verh: = h + 1;

Kemudian mengatur siklus "sampai bagian bawah adalah kurang dari batas atas":

Sementara Niz mulai

Pada setiap langkah, kita membagi segmen 2:

sredn: = (Niz + verh) div 2; {Gunakan fungsi div, karena kesenjangan tanpa sisa}

Setiap saat ulasan. Karena item telah ditemukan jika media yang diinginkan, mengganggu siklus:

jika sredn = isiko kemudian istirahat;

Jika elemen tengah array lebih dari yang diinginkan, membuang sisi kiri, yaitu, batas atas dari rata-rata menunjuk elemen:

jika Massiv [sredn]> isiko kemudian verh: = sredn;

Dan jika sebaliknya, itu membuat batas bawah:

lain Niz: = sredn;
berakhir;

Itu semua yang akan di program ini.

Mari kita mempertimbangkan bagaimana hal itu akan terlihat metode biner dalam praktek. Pertimbangkan array ini: 1, 3, 5, 7, 10, 12, 18 dan akan mencari nomor 12.

Secara total kami memiliki 7 elemen, sehingga akan media keempat, nilai 7.

Sejak lebih dari 12, 7, 1.3 dan 5 elemen, kita bisa membuang. Kemudian kita punya nomor 4, 4/2 tidak ada residu adalah 2. Jadi, elemen baru akan menjadi rata-rata 10.

Sejak 12 lebih besar dari 10, kita membuang 7. tetap hanya 10, 12 dan 18.

Di sini, unsur tengah sudah 12, itu adalah jumlah yang diperlukan. Tugas ini selesai - nomor 12 ditemukan.