Mustaqil ish bajardi: 111-20-guruh talabasi Baratboyev Jamshid Tekshirdi: Qayumov Oybek Achilovich. Jizzax 2021 Mаvzu: Chiziqli va Binar izlash algoritmlari. Mundarija: Kirish

2. Asosiy qism.
2.1.Reja1;
Chiziqli qidirish algoritmi qanday ishlaydi
Aytib o’tganimizdek, bu algoritm juda ham sodda ishlaydi va tasavvur qilishga ham oson.
Arrayning birinchi elementidan tekshirish boshlanadi.
Element olinadi va u berilgan shartga tekshirib ko’riladi.
Agar shartni qanoatlantirsa, uning qiymati yoki joylashgan o’rni (qiymati yoki shunchaki true) qaytariladi va algoritm tugaydi.
Shart qanoatlantirilmasa, keyingi elementga o’tiladi va 2-qadamga qaytiladi
Array tugab, element topilmasa, buni anglatuvchi qandaydir qiymat qaytariladi (-1 yoki false…)
Ko’rinishidan ko’pdek tuyulsa ham, aslida bu algoritm hayotdagi odatiy qidirish bilan bir xil ishlaydi. Keling uni visual holda tasavvur qilamiz.
Algoritm implementatsiyasiga o’zingiz mustaqil harakat qilib ko’ring, yoki keyingi videodarsimizga o’ting.
Algoritm murakkabligi
Chiziqli qidirish algoritmining vaqt bo’yicha murakkabligi uning nomidan ham ma’lum, ya’ni chiziqli O(n). Ya’ni, eng yomon holat sifatida element array bo’lmagan holat qaraladi va bunda algoritm maksimum n ta qadam ish bajarishi kerak bo’ladi.
Xotira jihatidan, algoritm ortiqcha joy talab qilmaydi.
Chiziqli qidirish algoritmi ko’pincha real hayotdagi holatlar uchun ancha sekinlik qiladi. Shuning uchun ham bunday holatlarda undan boshqa tezroq ishlaydigan algoritmlar qo’llanilishi kerak bo’ladi (masalan, ikkilik qidirish). Lekin, bu algoritmning ham ikkilik qidirishdan o’ziga yarasha avfzal tomonlari mavjud.


2.2.Reja2;
Ikkilik qidirish algoritmi ishlash prinsipi
Ikkilik qidirish algoritmini ishlash prinsipini tushunish uchun keling kompyuter bilan o’yin o’ynab ko’ramiz. O’yin shartlari quyidagicha:
Kompyuter 1 dan 100 gacha ixtiyoriy son tanlaydi. Sizning vazifangiz shu sonni iloji boricha kam taxmin ishlatgan holda topish.
Har bir taxmindan keyin kompyuter sizga sizning taxminingiz kompyuter o’ylagan sondan katta yoki kichikligini aytadi.
Agar sizning taxminingiz kompyuter o’ylagan son bilan bir xil bo’lsa, o’yin tugaydi.
Xo’sh, bunda kamroq yo’l tutish uchun nima qilgan bo’lar edingiz?
Albatta, birinchi navbatda o’rtadagi sonni taxmin qilib ko’ramiz, ya’ni 50 ni


Aytaylik kompyuter bizga taxminimiz o’ylangan sondan kichikroq ekanligini aytdi. Demak, endi biz 50 va undan kichik barcha son o’ylangan sondan kichik ekanligini bilamiz. Shunday qilib, bizning qidirish sohamiz ikki baravarga qisqaradi (50 ta son). Huddi shu tarzda davom etamiz. Endi 51 dan 100 gacha sonlar o’rtasidagi sonni olamiz, ya’ni 75 ni
Kompyuter bizga 75 o’ylangan sondan katta ekanligini aytdi. Demak, 75 dan katta barcha sonlar ham o’ylangan sondan katta ekan. Shunday qilib, bizdagi qidirish sohasi yana ikki baravarga qisqardi (25 ta son). Huddi shunday davom etib, biz o’ylangan sonni topishimiz mumkin.


Sonlar 100 ta bo’lgan holatda, biz har qanday tahminni ko’pi bilan 7 ta qadamda topishimiz mumkin bo’ladi.