Կարո՞ղ եք երկուական որոնել կապված ցուցակում:

2024 Հեղինակ: Lynn Donovan | [email protected]. Վերջին փոփոխված: 2023-12-15 23:48

Այո, Երկուական որոնում վրա հնարավոր է կապված ցուցակը, եթե որ ցուցակը պատվիրված է և դու իմանալ տարրերի քանակը ցուցակը . Բայց դասավորելիս ցուցակը , դու կարող ես մուտք գործել մեկ տարր միաժամանակ ցուցիչի միջոցով դեպի այդ հանգույցը, այսինքն՝ կամ նախորդ հանգույցը կամ հաջորդ հանգույցը:

Այսպիսով, ինչպիսի՞ն կլինի ժամանակի բարդությունը, երբ երկուական որոնումը կիրառվի կապված ցանկում:

Ժամանակի բարդություն չպետք է լինի O(log n)-ից ավելի: Ինչպես կապակցված ցուցակն անում է չտրամադրել պատահական մուտք, եթե մենք փորձենք դա անել կիրառել երկուական որոնում ալգորիթմ այն կամք հասնել O(n) ինչպես մեզ անհրաժեշտ է գտնել -ի երկարությունը ցուցակը և գնալ դեպի կեսը:

Նաև գիտեք, թե ինչպես է իրականացվում երկուական որոնումը: Երկուական որոնում : Որոնում տեսակավորված զանգված՝ բազմիցս բաժանելով որոնում ընդմիջումը կիսով չափ: Սկսեք ամբողջ զանգվածը ընդգրկող ընդմիջումով: Եթե արժեքը որոնում բանալին ավելի փոքր է, քան միջակայքի միջնամասում գտնվող կետը, նեղացրեք միջակայքը մինչև ստորին կեսը: Հակառակ դեպքում նեղացրեք այն վերին կեսին:

Հետևաբար, ո՞ր մեթոդն է օգտագործում երկուական որոնումը ցուցակում տարր գտնելու համար:

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

Ինչպե՞ս եք կրկնում կապակցված ցուցակի միջոցով:

Ան Իտերատոր կարող է օգտագործվել հանգույցի համար միջոցով ան LinkedList . hasNext() մեթոդը վերադարձնում է true, եթե այնտեղ ավելի շատ տարրեր կան LinkedList իսկ հակառակ դեպքում՝ կեղծ: Next() մեթոդը վերադարձնում է հաջորդ տարրը LinkedList և գցում է NoSuchElementException բացառությունը, եթե հաջորդ տարր չկա: