Carian binari - salah satu cara yang paling mudah untuk mencari elemen dalam array

Selalunya, pengaturcara, walaupun baru, berhadapan dengan hakikat bahawa terdapat satu set nombor, yang perlu mencari nombor tertentu. Ia adalah koleksi ini dipanggil array. Dan untuk mencari barang-barang di dalamnya, terdapat pelbagai cara. Tetapi mudah yang sebahagian besar daripada mereka boleh dianggap sebagai carian binari di sebelah kanan. Apakah kaedah ini? Dan bagaimana untuk melaksanakan carian binari? Pascal adalah persekitaran yang paling mudah untuk penganjuran program seperti itu, jadi kita akan menggunakannya untuk belajar.

Pertama, menganalisis, apakah kelebihan kaedah ini, ia adalah supaya kita boleh memahami, apa gunanya dalam kajian topik. Jadi, mari kita mempunyai pelbagai dengan dimensi sekurang-kurangnya 100000000 unsur-unsur, yang perlu mencari beberapa. Sudah tentu, masalah ini boleh diselesaikan dengan mudah dengan satu carian linear mudah, di mana kita menggunakan kitaran akan membandingkan unsur yang diperlukan dengan semua orang-orang yang berada di dalam array. Masalahnya ialah bahawa pelaksanaan idea ini akan mengambil masa yang terlalu lama. Dalam program Pascal mudah menjadi beberapa rawatan, dan tiga barisan teks utama, anda tidak akan melihat, tetapi apabila kita sampai kepada lebih kurang besar projek-projek dengan sebilangan besar cawangan dan fungsi yang baik, program ini akan bersedia untuk dimuatkan terlalu lama. Terutamanya jika komputer adalah prestasi yang lemah. Oleh itu, terdapat satu carian binari, yang mengurangkan masa carian sekurang-kurangnya dua kali.

Jadi, apa yang prinsip kerja kaedah ini? Segera ia tidak mengatakan bahawa carian binari berfungsi tidak ada di dalam mana-mana pelbagai, tetapi hanya pada set disusun nombor. Pada setiap langkah yang diambil unsur pertengahan array (bermaksud jumlah unsur). Jika diperlukan nombor adalah lebih besar daripada purata, maka apa yang tinggal, yang kurang daripada purata sel, boleh dibuang dan tidak melihat di sana. Sebaliknya, jika kurang daripada purata - antara nombor-nombor ke kanan, anda tidak boleh mencari. Kemudian pilih kawasan carian baru, di mana elemen pertama akan menjadi elemen pertengahan pelbagai keseluruhan, dan yang terakhir dan wasiat terakhir. Purata bilangan bidang baru akan ¼ semua segmen, iaitu, (elemen terakhir + unsur pertengahan pelbagai keseluruhan) / 2. Sekali lagi, operasi yang sama dilakukan - perbandingan dengan purata bilangan array. Jika nilai sasaran adalah kurang daripada purata, kita menolak sebelah kanan, dan juga yang perlu dilakukan seterusnya, sehingga kini unsur pertengahan ini tidak akan dikehendaki.

Sudah tentu, ia adalah yang terbaik untuk melihat contoh bagaimana untuk menulis carian binari. Pascal sini akan sesuai dengan sesiapa sahaja - versi tidak penting. Mari kita menulis program yang mudah.

Ia adalah pelbagai 1 hingga h di bawah nama "massiv", pembolehubah yang menunjukkan sempadan yang lebih rendah daripada carian, yang dipanggil "niz", had atas, yang dipanggil "verh", purata jangka carian - "sredn"; dan bilangan yang diperlukan - "ISK".

Jadi, pertama kita menetapkan had atas dan bawah carian julat:

niz: = 1;
verh: = h + 1;

Kemudian mengatur kitaran "sehingga bahagian bawah adalah kurang daripada had atas":

Manakala niz mula

Pada setiap langkah, kita membahagikan segmen 2:

sredn: = (niz + verh) div 2; {Gunakan div majlis itu, kerana jurang tanpa baki}

Setiap masa kajian semula. Kerana barang yang telah dijumpai jika medium yang diingini, mengganggu kitaran:

jika sredn = ISK maka akan dipatahkan;

Jika elemen tengah-tengah pelbagai yang lebih daripada yang dikehendaki, membuang sebelah kiri, iaitu, sempadan atas purata melantik elemen:

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

Dan jika sebaliknya, ia membuat sempadan yang lebih rendah:

lagi niz: = sredn;
berakhir;

Itu sahaja yang akan berada di program ini.

Mari kita kaji bagaimana ia akan kelihatan kaedah binari dalam amalan. Pertimbangkan pelbagai ini: 1, 3, 5, 7, 10, 12, 18 dan ia akan mendapatkan nombor 12.

Dalam jumlah kita ada 7 elemen, begitu juga medium keempat, nilai 7.

Sejak lebih daripada 12, 7, 1,3 dan 5 elemen, kita boleh buang. Maka kita telah mendapat nombor 4, 4/2 tiada sisa ialah 2. Jadi, elemen baru akan menjadi purata 10.

Sejak 12 adalah lebih besar daripada 10, kita membuang 7. kekal hanya 10, 12 dan 18.

Di sini, unsur tengah sudah 12, ia adalah nombor yang diperlukan. tugas ini selesai - Nombor 12 found.