Farg’ona davlat unversiteti Matematika-informatika fakulteti amaliy matematika yo’nalishi 20. 07 guruh talabasi Yangiboyev Kamoliddinning Algaritmik tillar fanidan “Heat ma'lumotlar tuzilmasi” mavzusida bajargan mustaqil ishi

Farg’ona davlat unversiteti Matematika-informatika fakulteti amaliy matematika yo’nalishi 20.07 guruh talabasi Yangiboyev Kamoliddinning Algaritim va berilganlar strukturasi fanidan “Interpolatsiya qidiruvi algaritmi” mavzusida bajargan mustaqil ishi

Interpolatsiya qidiruvi

• n ta teng taqsimlangan qiymatlardan iborat saralangan massiv berilgan arr[], massivda ma’lum bir x elementni qidirish funksiyasini yozing. Chiziqli qidiruv elementni O(n) vaqtida topadi, Jump Search O(√ n) vaqtni oladi va Binary Search O(log n) vaqtni oladi.
•  Interpolatsiya qidiruvi ikkilik qidiruvga nisbatan yaxshilanishdirmisol uchun, tartiblangan massivdagi qiymatlar bir xilda taqsimlangan. Interpolatsiya ma'lum ma'lumotlar nuqtalarining diskret to'plami oralig'ida yangi ma'lumotlar nuqtalarini yaratadi. Ikkilik qidiruv har doim tekshirish uchun o'rta elementga o'tadi. Boshqa tomondan, interpolatsiya qidiruvi qidirilayotgan kalitning qiymatiga qarab turli joylarga borishi mumkin. Misol uchun, agar kalitning qiymati oxirgi elementga yaqinroq bo'lsa, interpolatsiya qidiruvi oxirgi tomonda qidirishni boshlashi mumkin.
• Qidiriladigan pozitsiyani topish uchun u quyidagi formuladan foydalanadi. 

Turli xil interpolyatsiya usullari mavjud va ulardan biri chiziqli interpolyatsiya deb nomlanadi. Chiziqli interpolyatsiya biz (x1,y1) va (x2,y2) deb qabul qiladigan ikkita ma'lumot nuqtasini oladi va formulasi: (x,y) nuqtasida. Ushbu algoritm biz lug'atda so'zni qidiradigan tarzda ishlaydi. Interpolatsiya qidiruv algoritmi ikkilik qidiruv algoritmini yaxshilaydi. Qiymatni topish formulasi: K = ma'lumotlar-past/yuqori-past. K - qidiruv maydonini toraytirish uchun ishlatiladigan doimiy. Ikkilik qidiruvda bu konstantaning qiymati: K=(past+yuqori)/2.

Pos uchun formulani quyidagicha olish mumkin.

Algoritm :

• 1- qadam: Loopda prob pozitsiyasi formulasidan foydalanib, "pos" qiymatini hisoblang. 2- qadam: Agar u mos keladigan bo'lsa, element indeksini qaytaring va chiqing. 3-qadam: Agar element arr[pos] dan kichik bo'lsa, chap pastki massivning prob o'rnini hisoblang. Aks holda, o'ng pastki qatorda xuddi shunday hisoblang. 4-qadam : Moslik topilmaguncha yoki pastki massiv nolga tushguncha takrorlang.