Binary meklēšana - viens no vienkāršākajiem veidiem, lai atrastu elementu masīvā

Diezgan bieži, programmētāji, pat iesācējiem, saskaras ar to, ka tur ir skaitļu kopums, kas ir jāatrod konkrētu skaitu. Tā ir šī kolekcija sauc masīvs. Un, lai atrastu objektus tajā, ir neskaitāmas veidos. Bet visvienkāršākā no tām var uzskatīt par bināro meklēšanu labajā pusē. Kas ir šī metode ir? Un kā īstenot bināro meklēšanu? Pascal ir vieglākais vide organizācijai šādas programmas, lai mēs to izmantot, lai pētītu.

Pirmkārt, analizēt, kādas ir šīs metodes priekšrocības, tas ir, lai mēs varētu saprast, kāda jēga pētījumā par tēmu. Tātad, pieņemsim ir masīvs ar dimensijas vismaz 100000000 elementiem, kas nepieciešams, lai atrastu kādu. Protams, šo problēmu var viegli atrisināt ar vienkāršu lineāru meklēšanu, kurā mēs izmantojot ciklu salīdzinās nepieciešamo elementu ar visiem tiem, kas ir masīvā. Problēma ir tā, ka, īstenojot šo ideju prasīs pārāk daudz laika. Ar vienkāršu Pascal programmu par vairākām procedūrām, un trīs līnijas galvenajā tekstā, jums nav paziņojums, bet tad, kad mēs nonākam pie vairāk vai mazāk lielos projektos ar lielu filiāļu skaitu un labu funkcionalitāti, programma būs gatava iekraus pārāk ilgi. It īpaši, ja dators ir vājš sniegums. Tāpēc ir bināro meklēšanu, kas samazina meklēšanas laiku, vismaz divas reizes.

Tātad, kāda ir darba princips šo metodi? Uzreiz būtu teikt, ka bināro meklēšanas darbu nav nekāda masīvu, bet tikai par šķirotajiem skaitļu kopas. Katrā posmā ņemts no masīva vidējā elementa (nozīmē skaitu elementa). Ja nepieciešamais skaits ir lielāks nekā vidēji, tad viss, kas ir pa kreisi, kas ir mazāks nekā vidējais šūnā, var atcelt, un nevis meklēt tur. Savukārt, ja ir mazāk nekā vidēji - starp šiem skaitļiem pa labi, jūs nevarat meklēt. Pēc tam izvēlieties jaunu meklēšanas apgabalu, kur pirmais elements būs vidū visa masīva elements, un pēdējais, un pēdējās gribas. Vidējais skaits jaunajā jomā būs ¼ no visa segmentā, kas ir, (pēdējā elementa + vidējā visa masīva elementa) / 2. Atkal tas pats operācija tiek veikta - salīdzinājums ar vidējo skaitu masīva. Ja mērķa vērtība ir mazāka par vidējo, mēs noraidām labo pusi, un arī darīt tālāk, līdz šim tas vidū elements nebūtu vēlama.

Protams, vislabāk ir aplūkot piemēru, kā rakstīt bināro meklēšanu. Pascal šeit būs piemērots ikvienam - versija nav svarīgi. Pieņemsim uzrakstīt vienkāršu programmu.

Tas ir masīvs no 1 līdz h ar nosaukumu "Massiv", mainīga norādot apakšējo robežu meklēšanu, ko sauc par "niz", augšējā robeža, ko sauc par "Verh", vidējais meklēšanas termins - "sredn"; un vajadzīgo skaitu - "ISK".

Tātad, pirmkārt, mēs piešķirt augšējo un apakšējo robežu diapazona meklēšanu:

niz: = 1;
Verh: = h + 1;

Tad organizēt ciklu ", līdz apakšā ir mazāks par augšējo robežu":

Kaut niz sākt

Katrā posmā, mēs sadalīt segmentu 2:

sredn: = (niz + Verh) 2 div; {Izmantot funkciju div, jo dalījuma bez atlikuma}

Katra pārskata reizi. Jo vienums jau ir konstatēts, ja vide ir vēlama, pārtraukt ciklu:

іf sredn = ISK tad pārtraukums;

Ja vidū masīva elements vairāk nekā nepieciešams, atbrīvoties no kreisās puses, tas ir, augšējā robeža no vidējā nozīmēt elements:

ja Massiv [sredn]> ISK tad Verh: = sredn;

Un, ja tieši pretēji, tas padara apakšējo robežu:

cits niz: = sredn;
galu;

Tas ir viss, kas būs programmā.

Ļaujiet mums apsvērt, kā tas izskatīsies bināro metodi praksē. Apsveriet šo masīvu: 1, 3, 5, 7, 10, 12, 18, un tā centīsies numuru 12.

Kopumā mums ir 7 elementi, tāpēc būs ceturtais medijs, vērtību 7.

Tā kā vairāk nekā 12, 7, 1.3 un 5 elementiem, mēs varam atbrīvoties. Tad mēs esam ieguvuši skaits 4, 4/2 neviena atliekas ir 2. Tātad, jauns elements būs vidēji 10.

Tā kā 12 ir lielāks par 10, mēs izmestu 7. paliek tikai 10, 12 un 18.

Lūk, vidū elements ir jau 12, tas ir nepieciešams numurs. Šis uzdevums ir pabeigts - vairākas 12 atrasts.