|
Ózbekstan respublikasí sanli texnologiyalar ministrligi muhammed al-xorezmiy atindaǵÍ tashkent informaciyalíq texnologiyalarí universiteti nókis filialí telekommunikaciya texnologiyalari hám kásiplik tálim fakulteti «Informaciyalıq
|
| bet | 3/5 | | Sana | 01.11.2023 | | Hajmi | 264.17 Kb. | | #92450 |
Bog'liq Usnatdinov Islam Magliwmatlar strukturasi oz betinshe Faza va nol farqi, zazemleniya, anatatsiya, Yo\'l-yo\'l, Usnatdinov Islam Magliwmatlar strukturasi oz betinshe, Reja Mehnat unumdorligi va uning ahamiyati, Saliev mag.str word, essay, Qiziqarli fizika. PhysicsUzb , Atom yadro fizikasidan laboratoriya ishlari qo\'lanmasi, Nazirov Jamshid, 11-mavzu, Xf6v40aysSs CaTyRQfdkRubDxQNpheG (1), 26003769, 2-mavzu Sahna.3.Ekilik terek boyınsha izlew
Izlengen mánisti saralanǵan dizimniń ortadaǵı ma`nisi menen salıstırıw úsh qıylı nátiyje beriwi múmkin: bahalar teń, izlengen ma`nisi dizim elementinen kishi hám izlengen ma`nisi dizim elementinen úlken. Birinshi hám eń jaqsı halda izlew tawsıladı. Qalǵan eki halda dizim yarımın tastap jiberiwimiz múmkin. Eger maqset ma`nisi orta elementten kishi bolsa, ol halda ol bul orta element aldında jaylasqan boladı. Eger ol orta elementten úlken bolsa, ol halda ol orta elementten keyin jaylasqan boladı. Bul dizim yarımın tastap jiberiwge jetkiliklishe sebep boladı. Bul processni tákirarlap biz dizimdiń qalǵan bólimlerin yarımın tastap jiberiwimiz múmkin. Nátiyjede tómendegi algoritmǵa kelemiz:
BinarySearch(list,target,N)
list kórilip atırǵan dizim
target izlengen mánis
N dizim elementleri sanı start=1 end=N while start<=end do
middle=(start+end)/2
select(Compare(list[middle],target)) from
case -1: start=middle+1
case 0: return middle
case 1: end=middle-1
end select
end while
return 0
Bunda Compare(х,у) funksiyasi -1, 0 yaki 1 mánisleri mas túrde xy shártlerde beredi. Algoritmler analizinde Compare funksiyani shaqırıw bir salıstırıw deb esaplanadı.
Bul algoritmda eger izlengen mánis tabılǵan orta elementten úlken bolsa start ózgeriwshi middle ma`nisinen 1 den kóp mánis penen támiyinlenedi. Eger izlengen mánis tabılǵan orta elementten úlken bolsa end ózgeriwshi middle ma`nisinen 1 ge kemge támiyinlenedi. Jıljıw 1 bolsa orta element ızlenip atırǵan mániske teń bolmaǵan jaǵday menen tusintiriledi. Cikl mudamı toqtayma? Eger izlengen mánis tabılsa bunı return operatorı támiyinleydi. Eger kerekli mánis tabılmasa, ol halda hár bir cikl iteratsiyasında yamasa start dıń ma`nisi artadı yamasa start ózgeriwshiniń ma`nisi azayadı. Bul olardıń ma`nisi bir birine jaqınlasıwın kórsetedi. Qanday da jaǵdayda olar teńlesedi hám cikl start=end=middle de taǵı bir ret atqarıladı. Bul ótiwden keyin (eger izlenip atırǵan element bul indekske uyqas kelmese) yamasa start ma`nisi middle hám end lardan 1 ge úlken boladı, yamasa kerisi, end ózgeriwshi middle hám start lar ma`nisinen 1 ge kem boladı. Eki jaǵdayda da cikl while ótirik boladı hám cikl basqa atqarılmaydı. Sol sebepli cikl mudamı toqtaydı.
Algoritm har dayım dizimdi yarımǵa bóledi hám biz analizde qandaydur k ushın N=2k-1 dep oylayıq. Eger sonday bolsa, ekinshi ótiwde neshe element qaladı? Úshinshide ne? Ulıwma alǵanda, túsiniletuǵını, eger cikl qanday da ótiwde 2j-1 element dizim menen islese, ol jaǵdayda dizimniń birinshi yarmında 2j-1-1 element boladı, bir element ortada hám 2j-1-1 elementler dizimniń ekinshi yarmında boladı. Sonıń ushın keyingi otiwge 2j-1-1 element qaladı(1
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
Ózbekstan respublikasí sanli texnologiyalar ministrligi muhammed al-xorezmiy atindaǵÍ tashkent informaciyalíq texnologiyalarí universiteti nókis filialí telekommunikaciya texnologiyalari hám kásiplik tálim fakulteti «Informaciyalıq
|
