Binar search - salah siji saka cara paling gampang kanggo nggoleki unsur ing Uploaded

Cukup kerep, programer, malah wiwitan, ngadhepi karo kasunyatan sing ana pesawat saka nomer, kang kudu golek nomer tartamtu. Iku iki diarani Uploaded. Lan kanggo golek item ing iku, ana akeh cara. Nanging prasaja paling mau bisa dianggep telusuran binar ing sisih tengen. Apa cara iki? Lan carane kanggo ngleksanakake search binar? Pascal punika lingkungan paling gampang kanggo organisasi saka program kuwi, supaya kita bakal nggunakake aplikasi iku kanggo sinau.

First, njelasno, apa sing kaluwihan saka cara iki, iku supaya kita bisa ngerti, apa titik ing sinau saka topik. Dadi, ayo kang duwe Uploaded karo ukuran saka ing paling 100000000 unsur, kang kudu oleh. Mesthi, iki masalah bisa gampang ditanggulangi dening telusuran linear prasaja, kang kita nggunakake siklus bakal mbandhingaké unsur sing dijaluk karo kabeh sing ing Uploaded ing. Masalah iku ing implementasine saka idea iki bakal njupuk kakehan wektu. Ing program Pascal prasaja dadi sawetara pangobatan, lan telung baris saka teks utama, sampeyan ora bakal sok dong mirsani, nanging nalika kita teka menyang liyane utawa kurang gedhe proyèk karo nomer akeh cabang lan fungsi apik, program bakal siap kanggo dimuat kanggo dawa banget. Utamané yen komputer iku kinerja banget. Mulane, ana sing search binar, kang nyuda wektu search ing paling pindho.

Dadi, apa asas apa cara iki? Langsung iku kudu ngomong sing search binar dianggo ora ing Uploaded sembarang, nanging mung ing pesawat Kaurut nomer. Ing saben langkah dijupuk unsur tengah Uploaded ing (tegesipun nomer saka unsur). Yen dibutuhake nomer iku luwih saka rata-rata, banjur kabeh sing kiwa, sing kurang saka sèl saben, bisa dibuwak lan ora katon ana. Kosok baline, yen kurang saka rata-rata ing - antarane wong-wong nomer sisih tengen, sampeyan bisa ora golèk. Banjur pilih area search anyar, ngendi unsur pisanan bakal unsur tengah kabeh Uploaded, lan pungkasan lan bakal pungkasan. Nomer rata-rata lapangan anyar bakal ¼ kabeh babagan, sing, (unsur pungkasan + unsur tengah kabeh Uploaded) / 2. Maneh, padha operasi wis dileksanakake - comparison karo nomer rata-rata Uploaded ing. Yen Nilai target kurang saka rata-rata, kita nolak sisih tengen, lan uga kanggo apa sabanjuré, nganti saiki unsur tengah iki ora bakal dikarepake.

Mesthi, iku paling apik kanggo katon ing conto carane nulis search binar. Pascal kene bakal cocog karo sapa - versi ora penting. Ayo dadi nulis program prasaja.

Iku Uploaded 1 kanggo h miturut jeneng "massiv", a global nuduhake wates ngisor saka search, disebut "niz", ing watesan, disebut "verh", ing saben search term - "sredn"; lan nomer sing dibutuhake - "ISK".

Dadi, kita nemtokake wates ndhuwur lan ngisor saka search range:

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

Banjur ngatur siklus "nganti ngisor kurang saka wates ndhuwur":

Nalika niz miwiti

Ing saben langkah, kita dibagi babagan 2:

sredn: = (niz + verh) div 2; {Gunakake fungsi div, amarga sing dibagi tanpa seko}

Saben wektu review. Amarga item wis ketemu yen medium wis dikarepake, ngganggu siklus:

іf sredn = ISK banjur break;

Yen unsur tengah Uploaded liyane saka sing dipengini, discard ing sisih kiwa, sing, minangka wates ndhuwur sing rata-rata milih unsur:

yen massiv [sredn]> ISK banjur verh: = sredn;

Lan yen ing nalisir, iku ndadekake ing wates ngisor:

liya niz: = sredn;
mungkasi;

Sing kabeh sing bakal ing program.

Ayo kita nimbang carane bakal katon cara binar ing laku. Coba Uploaded iki: 1, 3, 5, 7, 10, 12, 18 lan iku bakal ngupaya nomer 12.

In total kita duwe 7 unsur, dadi bakal medium papat, nilai 7.

Luwih saka 12, 7, 1.3 lan 5 unsur, kita bisa discard. Banjur kita wis tak nomer 4, 4/2 ora turahan punika 2. Dadi, unsur anyar bakal Rata-rata 10.

Wiwit 12 iku luwih saka 10, kita discard 7. tetep mung 10, 12 lan 18.

Kene, unsur tengah wis 12, iku nomer sing dibutuhake. tugas iki rampung - nomer 12 ketemu.