#2 Izlew ha’m tan’law algoritmleri

#2 Izlew ha’m tan’law algoritmleri

Dizimdegi kerekli mag’liwmatlardi qidiriw teoriyaliq dasturlewdin’ waziypalarinin’ tiykarg’I na’rselerinen biri bolip esaplanadi. Qidiriw algoritmlerin taliqlap atirg’a waqitta, mag’liwmat bazi bir dizimdi payda etetin jaziwlarda bar bolg’an dep oylaymiz. Jaziwlar yamasa dizimler elementleri massivde jaylasqan boladi ha’m olar arasinda hesh qanday bosliq bolmawi kerek. Sanlardi jazamiz ha’m dizimde jaziwlardin’ uluwmaliq sani 1 den n ge shekem. Negizinde jaziwlar maydanlardan ibarat boliwi mu’mkin, biraq bizler ushin usi maydanlardan tek g’ana birewinin’ ma’nisine qizig’amiz. Ha’m bul gilt dep ataladi. Dizimler gilt maydanin’ ma’nisine qarap sortlanbag’an yamasa sortlang’an boliwi mu’mkin. Sortlanbag’an dizimde ma’nisler ta’rtipsiz jaylasqan boladi al sortlang’an o’siw ta’rtibinde dizimde izbe-iz jaylasqan boladi.

Sortlanbag’an dizimde kerek bolg’an gilt ma’nisin qidiriw dizimnin’ bar bolg’an elementlerin izlep atqan ma’niske ten’ bolaman degenshe ko’rip shig’iwdan ibarat boladi. Bul en’ an’sat ha’m a’piwayi algoritmlerden biri bolip esaplanadi. Bul algoritmnin’ effektivligi joqari emes ha’m ol ta’rtibsiz dizimde isleydi.

Sortlang’an dizimde ekilik qidiriw mu’mkin boladi. Ekilik qidiriwdi salistirsaq, onda izbe-iz jaylasqan elementlerden bir elemnti salistiriw ushin bir neshshe elementlerdi taslap qoyadi. Na’tiyjede qidiriw effektivli boladi.

Izbe-iz qidiriw algoritmi

Qidiriw algoritmlerinde bizge qandayda bir elementti izlewdegi dizimdi ko’rip shig’iw protsessi qiziq boladi. Biz bunda elementler dizimin sortlanbag’an dep esaplaymiz, sebebi bazi bir algoritmler sortlanbag’an dizimde effekti joqari boladi. Adette qidiriw izlep atirg’an giltimiz dizimde tek g’ana bar yamasa joq ekenligin aniqlaw esem yag’niy sol haqqinda toliq mag’liwmatqa iye boliw. Misali gilt ma’nis degenimiz jumisshinin’ nomeri yamasa tartib sani, yamasa basqa da identifikasiyon nomeri boliwi mu’mkin. Kerek bolg’an gilt aniqlang’annan son’ programma sol element benen baylanisli mag’liwmatlardi o’zgertiwge yamasa sol mag’liwmatlardi shig’arip beriwdi soraymiz. Izlew algoritminin’ maqsedi izlenip atirg’an giltimizdin’ jaylasqan ornin tawip beriwden ibarat boaldi. Sonliqdan qidiriw algoritmi dizimde indeksdi tawip beredi. Eger gilt ma’nis tawilmasa onda qidiriw algoritmi massivdin’ en’ joqarg’I shegarasinin’ u’stindegi indeksin shig’arip beredi. Dizimdegi jaziwlar 1 den n ge shekem bar bolsa biraq gilt ma’nisimiz joq bolsa onda bizge 0 ma’nisin qaytarip beredi. Izbe-iz qidiriw algoritmi dizimde birden baslap izlep atirg’an element tawilaman degenshe birme bir ko’rip shig’adi. Bunnan ko’rinip turipti gilt ma’nis dizimde turiwina baylanisili onin’ izlewine sonsha waqit ketedi.

Binar qidiriw algoritmi:

Belgilangan ro'yxatning o'rta elementi bilan maqsadli qiymatni taqqoslashda uchta natijadan bittasini olish mumkin: qiymatlar teng, maqsad qiymati ro'yxat elementidan kamroq yoki maqsad qiymati ro'yxat elementlaridan kattaroqdir. Birinchi va eng yaxshi holatda, qidiruv yakunlandi. Qolgan ikkita holatda biz ro'yxatning yarmini tushirishimiz mumkin.

Agar maqsad qiymati o'rta elementdan past bo'lsa, biz bilamizki, agar u ro'yxatda bo'lsa, u ushbu o'rta elementdan oldin. Agar u o'rta elementdan kattaroq bo'lsa, biz bilamizki, agar u ro'yxatda bo'lsa, unda bu o'rtadagi elementdan keyin. Bu bitta taqqoslash bilan biz ro'yxatning yarmini tashlab yuborishimiz uchun etarli. Ushbu protsedurani takrorlashda biz ro'yxatning qolgan qismini yarmiga tashlashimiz mumkin.