Երկուական որոնում մեկը ամենահեշտ ձեւերից է գտնել մի տարր է զանգված

Շատ հաճախ, ծրագրավորողներ, նույնիսկ սկսնակների, կանգնած է նրանով, որ կա մի շարք համարներ, որը պետք է գտնել մի կոնկրետ շարք: Դա այս հավաքածուն, որը կոչվում է զանգված. Եւ գտնել իրեր դրանից, կան մի անհամար ձեւերով: Սակայն առավել պարզ նրանցից կարելի է համարել որպես երկուական որոնումը աջ կողմում: Որն է այս մեթոդը. Եւ թե ինչպես պետք է իրականացնել երկուական որոնումը. Pascal է ամենահեշտ միջավայրը կազմակերպման համար նման մի ծրագրի, այնպես որ, մենք կօգտագործենք այն ուսումնասիրել.

Նախ, վերլուծել, թե ինչ են առավելությունները, այս մեթոդի, դա այդպես է, մենք կարող ենք հասկանալ, ինչ իմաստ է ուսումնասիրության թեման: Այնպես որ, եկեք ունեն զանգված հետ հարթություն առնվազն 100000000 տարրեր, որոնք պետք է գտնել որոշ. Իհարկե, այս խնդիրը կարող է հեշտությամբ լուծել `պարզ գծային որոնման, որը մենք օգտագործում ցիկլը կհամեմատենք անհրաժեշտ տարրը, ինչպես նաեւ բոլոր նրանց, ովքեր որ գտնվում են զանգված: Խնդիրն այն է, որ այս գաղափարի իրագործմանը պետք է շատ ժամանակ կպահանջվի: Մի պարզ Պասկալ ծրագրի մեջ մի քանի բուժում, եւ երեք գծերի հիմնական տեքստի, դուք չեք նկատում այն, բայց երբ մենք գալիս ենք մի ավելի կամ պակաս խոշոր նախագծերի հետ մեծ թվով մասնաճյուղերի եւ լավ ֆունկցիոնալությունը, որ ծրագիրը կլինի պատրաստ է բեռնվել համար չափազանց երկար է: Հատկապես, եթե համակարգիչը թույլ կատարումը: Հետեւաբար, կա մի երկուական որոնումը, որը նվազեցնում է որոնման ժամանակ առնվազն երկու անգամ:

Այնպես որ, թե ինչ է աշխատանքային սկզբունքը, այս մեթոդը. Անմիջապես պետք է ասեմ, որ երկուական որոնման աշխատում է ոչ թե որեւէ զանգված, բայց միայն մի տեսակավորված շարք թվերի: Յուրաքանչյուր քայլ ձեռնարկել միջին տարր զանգված (նկատի ունենալով համարը տարր): Եթե պահանջվող թիվն ավելի մեծ է, քան միջին, ապա այն ամենը, ինչ մնացել է, որ ավելի քիչ է, քան միջին խցում, կարող է անտեսվեցին, եւ ոչ թե նայում այնտեղ. Եվ հակառակը, եթե ավելի քիչ է, քան միջինը միջեւ այդ թվերի դեպի աջ, դուք չեք կարող որոնել. Ապա ընտրեք նոր որոնման տարածք, որտեղ առաջին տարրը կլինի միջին տարրը ողջ զանգված, իսկ վերջին, իսկ վերջինը կամքը: Միջին թվաքանակը նոր դաշտում կլինի քառորդ բոլոր հատվածի, այսինքն, (վերջին էլեմենտի + մեջտեղի տարր է ամբողջ զանգված) / 2: Կրկին, այդ նույն գործողությունը կատարվում, մի համեմատություն միջին թվով զանգված: Եթե թիրախ արժեքը պակաս է միջինը, մենք մերժում ենք աջ կողմում, ինչպես նաեւ անել, մինչեւ հիմա այդ մեջտեղի տարրը չէր ցանկալի.

Իհարկե, դա լավ է նայում մի օրինակ, թե ինչպես պետք է գրել երկուական որոնումը: Pascal Մականուն կլինի արժեքներ մեկին տարբերակը կարեւոր չէ: Եկեք գրել մի պարզ ծրագիր:

Դա մի զանգված 1-ից h անվան տակ «massiv», փոփոխական նշելով, ստորին սահմանը որոնման, որը կոչվում է «Niz», վերին սահմանը, որը կոչվում է «Verh», իսկ միջին որոնման տերմին «sredn». եւ անհրաժեշտ թվով «isk»:

Այնպես որ, առաջին հերթին մենք հանձնարարել վերին եւ ստորին սահմանը Լեռնաշղթայի որոնման

Niz: = 1;
Verh: = h + 1;

Ապա կազմակերպում է ցիկլը », մինչեւ ներքեւի ավելի քիչ է, քան վերին սահմանաչափի":

Մինչ Niz սկսել

Յուրաքանչյուր քայլ, մենք բաժանենք հատվածի 2:

sredn: = (Niz + Verh) div 2; {Օգտագործեք ֆունկցիայի div, քանի որ բաժանման առանց մնացած}

Ամեն անգամ, երբ վերանայման. Քանի որ նյութը արդեն գտել, եթե միջին ցանկալի է, ընդհատել ցիկլը:

եթե sredn = isk հետո կոտրել.

Եթե միջին տարրը զանգվածի ավելի քան ցանկալի, մերժել է ձախ կողմը, այսինքն, վերին սահմանը միջինը նշանակելու տարր:

եթե զանգվածում [sredn]> isk ապա Verh: = sredn;

Եւ եթե ընդհակառակը, այն կազմում է ստորին սահմանը:

ուրիշ Niz: = sredn;
վերջ;

Որ այդ ամենը կլինի ծրագրի.

Տեսնենք, թե ինչպես դա կանդրադառնա երկուական մեթոդը գործնականում: Մտածեք այս զանգված: 1, 3, 5, 7, 10, 12, 18, եւ դա կլինի ձգտում համարը 12:

Ընդհանուր առմամբ, մենք ունենք 7 տարրեր, ուստի պիտի չորրորդ միջին, արժեքը 7:

Քանի որ ավելի քան 12, 7, 1.3 եւ 5 տարրերի, մենք կարող ենք մերժել: Ապա մենք ստացել թիվ 4, 4/2, ոչ մնացորդի 2. Այսպիսով, նոր տարր չի լինի միջինը 10:

Քանի որ 12-ը ավելի մեծ է, քան 10, մենք դեն 7. մնում է միայն 10, 12 եւ 18:

Այստեղ է, որ միջին տարրը արդեն 12 է, այն է, որ անհրաժեշտ թվով: Այս խնդիրը ավարտվել համարը 12 found: