Օգտագործել երկուական որոնումը զանգվածի մեջ

Արի հասկանանք, թե ինչպես կարող ենք երկուական որոնումն օգտագործել տեսակավորված զանգվածում։ JavaScript-ն արդեն ունի մեթոդներ, որոնք ցույց է տալիս՝ արդյոք տարրը գտնվում է զանգվածում, թե ոչ, և գտնվելու դեպքում ցույց են տալիս զանգվածում տարրի դիրքը։ Այս դեպքում, սակայն, մենք պետք է ձեռքով այն կառուցենք, որպեսզի ամբողջությամբ հասկանանք այդպիսի մեթոդները և դրանց օգտագործումը։ Ահա JavaScript-ի զանգված՝ կազմված աճման կարգով դասավորված առաջին 25 պարզ թվերից (var-ը անգլերեն օգտագործվում է որպես փոփոխական, primes-ը՝ պարզ)․

Ենթադրենք, ուզում ենք իմանալ, թե պարզ թիվ է արդյոք 67-ը։ Եթե 67-ը մեր զանգվածի մեջ է, այն պարզ թիվ է։

Գուցե մենք ուզում ենք նաև ճշտել, թե մինչև 67-ը քանի պարզ թիվ կա։ Եթե գտնենք 67-ի դիրքը զանգվածում, դա նաև ցույց կտա, թե մինչև այդ թիվը քանի պարզ թիվ կա։

Զանգվածում տարրի դիրքը կոչվում է ցուցիչ(index)։ Զանգվածի ցուցիչները սկսվում են 0-ից։ Եթե տարրի ցուցիչը 0 է, ապա այն զանգվածի առաջին տարրն է։ Եթե տարրի ցուցիչը 3 է, ապա զանգվածում դրանից ձախ կա 3 տարր։

Ինչպես ներքևի օրինակում, մենք կարող ենք գտնել 67 թիվը՝ ձախից հերթով փնտրելով այն, և տեսնել, որ դրա ցուցիչը 18-ն է։ Զանգվածի մեջ հերթով ձախից աջ փնտրելը կոչվում է գծային որոնում (linear search)։

Քանի որ արդեն գիտենք, որ 67-ի ցուցիչը 18-ն է, կարող ենք ասել, որ այն պարզ թիվ է։ Նաև կարող ենք ասել, որ մինչև 67-ը զանգվածում կա 18 տարր, ինչը նշանակում է, որ կա 18 պարզ թիվ, որոնք փոքր են 67-ից։

Տեսա՞ր՝ քանի քայլից գտանք այդ թիվը։ Երկուական որոնումով միանշանակ ավելի արագ կգտնեինք։ Քանի որ primes զանգվածում կա 25 թիվ, դրա ցուցիչները 0-ից 24 թվերն են։ Օգտագործելով մեր կեղծ կոդը՝ վերագրում ենք min = 0 և max = 24։ Ըստ երկուական որոնման՝ առաջին գուշակումը պետք է լինի 12 (այսինքն՝ (0 + 24) / 2)։ Ստուգում ենք՝ արդյոք primes[12]-ը հավասար է 67։ Ոչ, primes[12]-ը հավասար է 41։

Այն ցուցիչը, որը փնտրում ենք, մե՞ծ է, թե՞ փոքր 12-ից։ Քանի որ արժեքները դասավորված են աճման կարգով և 41 < 67, ուրեմն 67-ը պետք է գտնվի 12\ ցուցչից աջ։ Այլ կերպ ասած՝ մենք պետք է գուշակենք 12-ից մեծ թիվ։ Մեր min-ի արժեքին վերագրում ենք 12 + 1, այսինքն՝ 13, իսկ max-ը թողնում ենք 24։

Հիմա ո՞ր ցուցիչը պետք է գուշակենք։ 13-ի ու 24-ի միջինը 18,5-ն է, որը կլորացնում ենք 18 (դեպի ներքև), քանի որ ցուցիչը պետք է լինի ամբողջ թիվ։ Եվ գտնում ենք, որ primes[18]-ը 67-ն է։

Երկուական որոնում ալգորիթմը կանգնում է այն ժամանակ, երբ գտնում է պատասխանը։ Մենք գտանք այն երկու քայլով, մինչդեռ գծային որոնումով պահանջվեց 19 քայլ։ Դու կարող ես նույնը պատկերավոր տեսնել այստեղ․

Մի օրինակի միջոցով մենք հայերենով փորձեցինք բացատրել երկուական որոնման գաղափարը, սակայն մարդու լեզվով բացատրածը երբեմն կարող է թերի լինել։ Այն կարող է լինել շատ կարճ կամ շատ երկար է ամենակարևորը, միշտ չէ, որ կարող է ունենալ հստակ բացարտրություն։ Մենք միանգամից քեզ ցույց կտանք, թե ինչպես օգտագործել երկուական որոնումը ծրագրավորման լեզուների մեջ, ինչպիսիք են JavaScript-ը կամ Python-ը։ Սակայն հաշվի առ, որ ծրագրերում հիմնականում լինում են բազում մանրամասներ՝ կախված ծրագրավորման լեզվի պահանջներից։ Շատ հաճախ ծրագրերը առնչություն են ունենում տարբեր խնդիրների հետ, որոնք առաջանում են թերի տվյալների կամ ընդհանուր ծրագրային խափանումից և կոդի ուսումնասիրությունը կարող է բավարար չլինել ուսումնասիրելու առկա ալգորիթմը։ Այդ իսկ պատճառով մենք նախընտրում ենք նկարագրել ալգորիթմները կեղծ կոդերի միջոցով (pseudocode), որտեղ անգլերենի որոշ հատկություններ խառնվում են ծրագրավորման լեզուների հետ։

Ահա ձևափոխված երկուական որոնման կեղծ կոդը՝ զանգվածում որոնում կատարելու համար։ Մուտքագված արժեքները կանվանենք array (զանգվածի անգլերեն բառը), n-ը array-ի տարրերի քանակն է, և target-ն այն թիվն է, որը փնտրում ենք։ Իսկ արդյունքը կլինի array-ում target-ի ցուցիչը․

Այս դասընթացում կախված իրավիճակից մենք կկիրառենք մեկընդմեջ հայերեն, անգլերեն, կեղծ կոդ և JavaScript։ Որպես ծրագրավորող՝ դու պետք է հասկանաս, թե ինչ է գրված կեղծ կոդում և կարողանաս այն վերածել կոդի, հետևաբար, չնայած մենք օգտագործում ենք JavaScript, պետք է կարողանաս կեղծ կոդը վերածել ցանկացած այլ լեզվի։

Ինչպե՞ս ենք կեղծ կոդը դարձնում JavaScript-ի ծրագիր։ Մենք պետք է ստեղծենք ֆունկցիա, քանի որ գրում ենք կոդ, որն ընդունում և վերադարձնում է արժեք, և ուզում ենք, որ կոդն աշխատի բոլոր տեսակի հնարավոր մուտքագրված արժեքների դեպքում։ Ֆունկցիան կանվանենք binarySearch, որի պարամետրերը կլինեն array-ն ու target-ը, իսկ ֆունկցիան կվերադարձնի գտած տարրի ցուցչի արժեքը։

Հիմա արի տեսնենք, թե ինչ է կատարվում ֆունկցիայի մարմնում, և ինչպես կարող ենք այն օգտագործել։ Քայլ 6-ում գրված է, որ պետք է վերադառնաս քայլ 2։ Կարծես թե պետք է ցիկլ օգտագործենք։ Իսկ ի՞նչ օգտագործել այս դեպքում՝ for ցիկլ, թե՞ while ցիկլ։ Եթե դու անչափ շատ ես ուզում օգտագործել for ցիկլ, կարող ես օգտագործել, բայց երկուական որոնման դեպքում ցուցիչները գուշակելիս մեր գուշակած թվերն աճման կամ նվազման կարգով չեն լինում։ Սկզբում, օրինակ՝ գուշակում ենք 12, հետո՝ 18, և այսպես շարունակ՝ օգտագործելով որոշ հաշվարկներ։ Հետևաբար, այս դեպքում while ցիկլն ավելի ցանկալի տարբերակ է։

Կեղծ կոդում պակասում է նաև մի կարևոր քայլ, որն այս խաղի համար կարևոր չէ, բայց կարևոր է զանգվածում երկուական որոնումը հասկանալու համար։ Ի՞նչ կլինի, եթե այն թիվը, որը փնտրում ես, զանգվածում չէ։ Արի սկզբում հասկանանք, թե binarySearch ֆունկցիան ինչ ցուցիչ է վերադարձնում այս դեպքում։ Պետք է լինի ցուցիչ, որն արգելվում է օգտագործել զանգվածում։ Մենք կվերցնենք -1 թիվը, քանի որ զանգվածը չի կարող բացասական թիվ ընդունել (իրականում ցանկացած բացասական թվի համար կաշխատեր)։

Փնտրվող թիվը զանգվածում չէ այն դեպքում, երբ զանգվածի բոլոր թվերը կռահելուց հետո չենք գտել այն։ Մեր օրինակում պատկերացրու փնտրում ենք 10 թիվը primes զանգվածում։ Եթե 10-ն այդտեղ լիներ, այն կլիներ 7-ի ու 11-ի միջև, որոնց ցուցիչները 3-ն ու 4-ն են։ Եթե min-ի ու max-ի արժեքներն անընդհատ ըստ binarySearch ֆունկցիայի կանոնների նոր ցուցիչներ վերագրենք, որոշակի քայլերից հետո min-ը կլինի 3, իսկ max-ը՝ 4։ Ցուցիչ 3-ը կլինի մեր հաջորդ կռահումը (քանի որ (3 + 4) / 2-ը հավասար է 3,5, ու կլորացնում ենք դեպի ներքև), ևprimes[3]-ը փոքր է 10-ից, հետևաբար min-ը դառնում է 4։ Ստանում ենք այն դեպքը, երբ min-ն ու max-ը հավասար են 4-ի, հետևաբար պետք է կռահենք 4, իսկ primes[4]-ը մեծ է 10-ից։ Հիմա էլ max-ն է դառնում 3։ Ի՞նչ է նշանակում, եթե ստանում ենք min-ը հավասար է 4-ի, իսկ max-ը՝ 3-ի։ Նշանակում է, որ հնարավոր տարբերակների նվազագույն արժեքը 4-ն է, իսկ առավելագույնը՝ 3-ը։ Չկան այդպիսի թվեր։ Այստեղ արդեն կարող ենք եզրակացնել, որ մեր փնտրվող (target) թիվը՝ 10-ը, primes զանգվածում չէ, իսկ binarySearch ֆունկցիան կվերադարձնի -1։ Հիմնականում, երբ max-ը դառնում է min-ից փոքր, նշանակում է, որ թիվը չկա տեսակավորված զանգվածում։ Ահա երկուական որոնման ձևափոխված կեղծ կոդը, որը նաև հաշվի է առնում այն դեպքը, երբ թիվը զանգվածում չէ․

Հիմա, երբ մենք կեղծ կոդն ամբողջությամբ ի մի բերեցինք, դու կփորձես ինքնուրույն գրել երկուական որոնման կոդը։ Կոդը գրելու ժամանակ օգտագործիր կեղծ կոդը, քանի որ դրանով ավելի կամրապնդես գիտելիքներդ երկուական որոնման մասին և առհասարակ կունենաս ընդհանուր գաղափար կեղծ կոդը կոդի վերածելու մասին։

Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։