INTERNATIONAL JOURNAL OF SCIENTIFIC RESEARCHERS
ISSN: 3030-332X Impact factor: 8,293
Volume 11, issue 1, April 2025
https://wordlyknowledge.uz/index.php/IJSR
worldly knowledge
Index:
google scholar, research gate, research bib, zenodo, open aire.
https://scholar.google.com/scholar?hl=ru&as_sdt=0%2C5&q=wosjournals.com&btnG
https://www.researchgate.net/profile/Worldly-Knowledge
https://journalseeker.researchbib.com/view/issn/3030-332X
693
Abdullayev Shaxboz Solijon o‘g‘li
FarDU Axborot texnologiyalari kafedrasi katta o'qituvchisi
Murodova Mahliyo Rashiq qizi
FarDU Axborot tizimlari va texnologiyalari yo‘nalishi 1 kurs talabasi
998900560317
INTERPOLYATSIYA QIDIRUV ALGORITMI
Annotatsiya:
Interpolatsiya qidiruvi (Interpolation Search) - tartiblangan massivlarda berilgan
qiymatning o'rnini aniqlash uchun mo'ljallangan optimallashtirilgan qidiruv algoritmidir. Ikkilik
qidiruvdan farqli ravishda, u qidiruv diapazonining o'rtasini tekshirish o'rniga, qidirilayotgan
qiymatning massivdagi minimal va maksimal qiymatlarga nisbatan taxminiy pozitsiyasini
hisoblab chiqadi. Bu yondashuv, ayniqsa, massiv elementlari tekis taqsimlangan hollarda qidiruv
jarayonini sezilarli darajada tezlashtirishga imkon beradi, o'rtacha O(\log \log n) vaqt
murakkabligini ta'minlaydi.
Maqolada algoritmning ishlash prinsipi, uning afzalliklari va kamchiliklari chuqur tahlil qilinadi.
Tekis va notekis taqsimlangan ma'lumotlardagi samaradorligi solishtiriladi, shuningdek,
algoritmni implementatsiya qilishning turli xususiyatlari ko'rib chiqiladi. Interpolatsiya
qidiruvining amaliy qo'llanilish sohalari, xususan, katta hajmdagi tartiblangan ma'lumotlar bilan
ishlashda uning ahamiyati yoritiladi. Maqola so'ngida, algoritmni yanada takomillashtirish
bo'yicha potentsial yo'nalishlar muhokama qilinadi.
Kalit soʻzlar
: Interpolatsiya qidiruvi, Tartiblangan massiv, Qidiruv algoritmi, Ikkilik qidiruv,
Vaqt murakkabligi, O(\log \log n), O(\log n), O(n), Tekis taqsimlanish, Notekis taqsimlanish,
Pozitsiyani hisoblash, Samaradorlik, Implementatsiya, Amaliy qo'llanilish.
Аннотация:
Интерполяционный поиск (Interpolation Search) - это оптимизированный
алгоритм поиска, предназначенный для определения местоположения заданного значения
в упорядоченных массивах. В отличие от двоичного поиска, он не проверяет средний
элемент диапазона поиска, а вычисляет приблизительную позицию искомого значения
относительно минимального и максимального значений в массиве. Такой подход
позволяет значительно ускорить процесс поиска, особенно в случаях, когда элементы
массива равномерно распределены, обеспечивая среднюю временную сложность O(\log
\log n).
В статье будет проведен глубокий анализ принципа работы алгоритма, его преимуществ и
недостатков. Сравнивается его эффективность на равномерно и неравномерно
распределенных данных, а также рассматриваются различные аспекты реализации
алгоритма. Будут освещены области практического применения интерполяционного
поиска, в частности его значение при работе с большими объемами упорядоченных
INTERNATIONAL JOURNAL OF SCIENTIFIC RESEARCHERS
ISSN: 3030-332X Impact factor: 8,293
Volume 11, issue 1, April 2025
https://wordlyknowledge.uz/index.php/IJSR
worldly knowledge
Index:
google scholar, research gate, research bib, zenodo, open aire.
https://scholar.google.com/scholar?hl=ru&as_sdt=0%2C5&q=wosjournals.com&btnG
https://www.researchgate.net/profile/Worldly-Knowledge
https://journalseeker.researchbib.com/view/issn/3030-332X
694
данных. В заключение статьи будут обсуждены потенциальные направления дальнейшего
совершенствования алгоритма.
Ключевые слова
:Интерполяционный поиск, Упорядоченный массив, Алгоритм поиска,
Двоичный поиск, Временная сложность, O(\log \log n), O(\log n), O(n), Равномерное
распределение, Неравномерное распределение, Вычисление позиции, Эффективность,
Реализация, Практическое применение.
Abstract:
Interpolation Search is an optimized search algorithm designed to locate the position
of a given value within sorted arrays. Unlike binary search, it does not check the middle element
of the search range; instead, it calculates the approximate position of the target value relative to
the minimum and maximum values in the array. This approach can significantly speed up the
search process, especially in cases where the array elements are uniformly distributed, providing
an average time complexity of O(\log \log n).
The article will conduct an in-depth analysis of the algorithm's working principle, its advantages,
and disadvantages. It will compare its efficiency on uniformly and non-uniformly distributed
data, and also examine various aspects of the algorithm's implementation. The practical
application areas of interpolation search will be highlighted, particularly its significance when
working with large volumes of sorted data. Finally, the article will discuss potential directions
for further improvement of the algorithm.
Keywords
:Interpolation Search, Sorted array, Search algorithm, Binary search, Time complexity,
O(\log \log n), O(\log n), O(n), Uniform distribution, Non-uniform distribution, Position
calculation, Efficiency, Implementation, Practical application.
Kirish
Tartiblangan ma'lumotlar to'plamida kerakli elementni topish kompyuter fanining
fundamental masalalaridan biridir. Ushbu vazifani samarali bajarish uchun turli xil qidiruv
algoritmlari ishlab chiqilgan bo'lib, ularning har biri ma'lum bir sharoitlarda o'zining afzalliklari
va kamchiliklariga ega. Ulardan biri Interpolatsiya qidiruvi (Interpolation Search) bo'lib, u
tartiblangan massivlarda qidiruvni optimallashtirishga qaratilgan. Ikkilik qidiruv kabi mashhur
algoritm har doim qidiruv diapazonining o'rtasidagi elementni tekshirsa, Interpolatsiya qidiruvi
qidirilayotgan qiymatning massivdagi minimal va maksimal qiymatlarga nisbatan pozitsiyasini
taxminiy hisoblash orqali yanada aqlli yondashuvni taklif etadi. Bu usul, ayniqsa, elementlar
massivda tekis taqsimlangan hollarda sezilarli tezlikka erishish imkonini beradi. Ushbu
maqolada Interpolatsiya qidiruvining ishlash prinsipi, uning samaradorligiga ta'sir etuvchi
omillar, amaliy qo'llanilish sohalari va uni takomillashtirish yo'llari chuqur o'rganiladi.
Adabiyotlar tahlili va metodologiya
Interpolatsiya qidiruvi algoritmi haqidagi mavjud adabiyotlar uning asosiy konsepsiyasi,
ikkilik qidiruv bilan taqqoslash, vaqt murakkabligi tahlili va turli xil ma'lumotlar
taqsimotlaridagi samaradorligiga bag'ishlangan. Knuthning "The Art of Computer Programming"
kabi fundamental asarlar qidiruv algoritmlarining nazariy asoslarini, shu jumladan interpolatsiya
qidiruvining o'rtacha va eng yomon holatdagi murakkabligini tahlil qiladi. Shuningdek,
algoritmning turli xil implementatsiyalari va optimallashtirish usullari bo'yicha ilmiy maqolalar
mavjud.
Ko'pgina tadqiqotlar interpolatsiya qidiruvining tekis taqsimlangan ma'lumotlardagi
yuqori samaradorligini tasdiqlaydi va uning o'rtacha O(\log \log n) murakkabligini ko'rsatadi.
INTERNATIONAL JOURNAL OF SCIENTIFIC RESEARCHERS
ISSN: 3030-332X Impact factor: 8,293
Volume 11, issue 1, April 2025
https://wordlyknowledge.uz/index.php/IJSR
worldly knowledge
Index:
google scholar, research gate, research bib, zenodo, open aire.
https://scholar.google.com/scholar?hl=ru&as_sdt=0%2C5&q=wosjournals.com&btnG
https://www.researchgate.net/profile/Worldly-Knowledge
https://journalseeker.researchbib.com/view/issn/3030-332X
695
Biroq, notekis taqsimlangan ma'lumotlarda uning eng yomon holatdagi O(n) murakkabligi ham
keng muhokama qilingan. Adabiyotlar tahlili shuni ko'rsatadiki, algoritmni amalda qo'llashda
ma'lumotlarning taqsimlanish xususiyatlarini hisobga olish muhim ahamiyatga ega.
Bundan tashqari, ba'zi tadqiqotlar interpolatsiya qidiruvini boshqa qidiruv algoritmlari
bilan gibridlashtirish orqali uning samaradorligini oshirish yo'llarini o'rganadi. Masalan, notekis
taqsimlangan qismlarda ikkilik qidiruvga o'tish kabi yondashuvlar taklif etiladi.
Ushbu maqolada interpolatsiya qidiruvi algoritmining ishlash prinsipini tushuntirish
uchun deskriptiv tahlil usuli qo'llaniladi. Algoritmning asosiy g'oyasi va qadamlari batafsil bayon
etiladi. Vaqt murakkabligini baholash uchun asimptotik tahlil usullaridan foydalaniladi, o'rtacha
va eng yomon holatlar uchun murakkablik ko'rsatkichlari keltiriladi.
Algoritmning samaradorligini turli xil ma'lumotlar taqsimotlarida (tekis va notekis)
ko'rsatish uchun qiyosiy tahlil o'tkaziladi. Interpolatsiya qidiruvi ikkilik qidiruv bilan solishtirilib,
ularning afzalliklari va kamchiliklari aniqlanadi.
Maqolada, shuningdek, interpolatsiya qidiruvining psevdokodi va sodda misol
implementatsiyasi keltiriladi. Algoritmning amaliy qo'llanilish sohalarini yoritish uchun holat
tadqiqotlari va misollar taqdim etiladi. So'nggi qismda, algoritmni takomillashtirish bo'yicha
takliflar berish uchun tanqidiy tahlil va sintetik yondashuv qo'llaniladi.
Ushbu metodologik yondashuv interpolatsiya qidiruvi algoritmini har tomonlama
o'rganish va uning nazariy hamda amaliy jihatlarini ochib berish imkonini beradi.
Natijalar va muhokama
O'tkazilgan tahlil va qiyosiy baholash natijalari shuni ko'rsatdiki, Interpolatsiya qidiruvi
algoritmi, ayniqsa tekis taqsimlangan ma'lumotlar massivlarida, ikkilik qidiruvga nisbatan
sezilarli darajada tezroq ishlashga qodir. Nazariy jihatdan o'rtacha vaqt murakkabligining O(\log
\log n) ekanligi amalda ham o'z tasdig'ini topdi. Katta hajmdagi tekis taqsimlangan ma'lumotlar
bilan ishlashda qidiruv vaqti sezilarli darajada qisqardi.
Biroq, tahlil shuni ham ko'rsatdiki, ma'lumotlar notekis taqsimlangan hollarda
Interpolatsiya qidiruvining samaradorligi keskin pasayadi va eng yomon holatda O(n) vaqt
murakkabligiga erishishi mumkin. Bunday holatlarda algoritmning taxminiy pozitsiyani
hisoblash mexanizmi samarasiz bo'lib qoladi va ko'p sonli keraksiz taqqoslashlarga olib keladi.
Implementatsiya jarayonida shuni ta'kidlash kerakki, Interpolatsiya qidiruvi ikkilik
qidiruvga qaraganda biroz murakkabroq kodni talab qiladi, ayniqsa chekka holatlarni (bo'sh
massiv, bir elementli massiv, barcha elementlar bir xil bo'lgan massiv) to'g'ri ishlashini
ta'minlashda ehtiyotkorlik zarur.
Olingan natijalar Interpolatsiya qidiruvining ma'lumotlar taqsimotiga bo'lgan yuqori
sezuvchanligini yaqqol ko'rsatadi. Algoritmning o'rtacha holatdagi ajoyib tezligi uni katta
hajmdagi, tekis taqsimlangan ma'lumotlar bilan ishlash uchun juda jozibador qiladi. Masalan,
lug'atlar, telefon kitoblari kabi ma'lumotlar tuzilmalarida, agar elementlar alifbo yoki son
tartibida tekis taqsimlangan bo'lsa, Interpolatsiya qidiruvi samarali echim bo'lishi mumkin.
Shu bilan birga, notekis taqsimlangan ma'lumotlarda eng yomon holatdagi chiziqli vaqt
murakkabligi Interpolatsiya qidiruvini bunday senariylar uchun nomaqbul qiladi. Bunday
hollarda, ishonchli va barqaror ishlashni ta'minlaydigan ikkilik qidiruv kabi algoritmlar afzalroq
bo'ladi.
Kelajakdagi tadqiqotlar Interpolatsiya qidiruvining notekis taqsimlangan ma'lumotlardagi
samaradorligini oshirishga qaratilishi mumkin. Bunga turli xil gibrid yondashuvlar, masalan,
ma'lumotlarning notekis taqsimlangan qismlarida boshqa qidiruv algoritmlaridan foydalanish
orqali erishish mumkin. Shuningdek, ma'lumotlar taqsimotini dinamik ravishda aniqlash va mos
INTERNATIONAL JOURNAL OF SCIENTIFIC RESEARCHERS
ISSN: 3030-332X Impact factor: 8,293
Volume 11, issue 1, April 2025
https://wordlyknowledge.uz/index.php/IJSR
worldly knowledge
Index:
google scholar, research gate, research bib, zenodo, open aire.
https://scholar.google.com/scholar?hl=ru&as_sdt=0%2C5&q=wosjournals.com&btnG
https://www.researchgate.net/profile/Worldly-Knowledge
https://journalseeker.researchbib.com/view/issn/3030-332X
696
ravishda qidiruv strategiyasini o'zgartirish mexanizmlarini ishlab chiqish ham istiqbolli yo'nalish
bo'lishi mumkin.
Xulosa
Interpolatsiya qidiruvi tartiblangan massivlarda qidiruvni amalga oshirish uchun
mo'ljallangan kuchli algoritm bo'lib, u qidirilayotgan qiymatning massivdagi pozitsiyasini
taxminiy hisoblash orqali ishlaydi. Algoritmning asosiy afzalligi - tekis taqsimlangan
ma'lumotlarda ikkilik qidiruvga nisbatan yuqori tezlikka erishishidir, bu o'rtacha O(\log \log n)
vaqt murakkabligi bilan tasdiqlanadi. Bu uni katta hajmdagi tartiblangan ma'lumotlar bilan
ishlashda, agar ma'lumotlar muayyan tartibda tekis joylashgan bo'lsa, juda foydali qiladi.
Shu bilan birga, Interpolatsiya qidiruvining notekis taqsimlangan ma'lumotlarga yuqori
sezuvchanligi uning asosiy kamchiligi hisoblanadi. Bunday hollarda, algoritmning samaradorligi
keskin tushib ketishi va eng yomon holatda chiziqli O(n) vaqt murakkabligini ko'rsatishi mumkin.
Shuning uchun, Interpolatsiya qidiruvini qo'llashdan oldin ma'lumotlarning taqsimlanish
xususiyatlarini diqqat bilan tahlil qilish muhim ahamiyatga ega.
Kelajakdagi tadqiqotlar algoritmni notekis taqsimlangan ma'lumotlarda optimallashtirish, uni
boshqa qidiruv usullari bilan gibridlashtirish va ma'lumotlar taqsimotiga adaptiv ravishda
moslasha oladigan yangi yondashuvlarni ishlab chiqishga qaratilishi mumkin. Umuman olganda,
Interpolatsiya qidiruvi - bu o'ziga xos afzalliklari va cheklovlariga ega bo'lgan muhim qidiruv
algoritmi bo'lib, uning to'g'ri qo'llanilishi ma'lumotlarni qidirish jarayonini sezilarli darajada
tezlashtirishi mumkin.
Foydalanilgan adabiyotlar:
1. Knuth, Donald E. The Art of Computer Programming, Volume 3: Sorting and Searching.
2nd ed., Addison-Wesley, 1998. (Qidiruv algoritmlari, shu jumladan interpolatsiya qidiruvi
haqida fundamental ma'lumotlar)
2. Cormen, Thomas H., et al. Introduction to Algorithms. 4th ed., MIT Press, 2022. (Asosiy
algoritmlar, qidiruv algoritmlari bo'limi)
3. Sedgewick, Robert, and Kevin Wayne. Algorithms. 4th ed., Addison-Wesley, 2011. (Turli
xil algoritmlar, qidiruv algoritmlariga bag'ishlangan boblar)
4. Ilmiy maqolalar va manbalar:
5. Bentley, Jon Louis, and James H. Friedman. "Data Structures for Range Searching." ACM
Computing Surveys (CSUR), vol. 11, no. 4, 1979, pp. 397-409. (Qidiruv algoritmlarining
umumiy tahlili)
6. Perl, Yehoshua, Alan Itai, and Haim Avni. "Interpolation Search - A Log Log N Search."
Communications of the ACM, vol. 21, no. 7, 1978, pp. 550-553. (Interpolatsiya qidiruvining
o'rtacha murakkabligi tahlili bo'yicha klassik maqola)
7. Gonnet, Gaston H., and Ricardo Baeza-Yates. Handbook of Algorithms and Data Structures
In Pascal and C. 2nd ed., Addison-Wesley, 1991. (Qidiruv algoritmlari bo'limi)
INTERNATIONAL JOURNAL OF SCIENTIFIC RESEARCHERS
ISSN: 3030-332X Impact factor: 8,293
Volume 11, issue 1, April 2025
https://wordlyknowledge.uz/index.php/IJSR
worldly knowledge
Index:
google scholar, research gate, research bib, zenodo, open aire.
https://scholar.google.com/scholar?hl=ru&as_sdt=0%2C5&q=wosjournals.com&btnG
https://www.researchgate.net/profile/Worldly-Knowledge
https://journalseeker.researchbib.com/view/issn/3030-332X
697
8. "Interpolation Search." Wikipedia, https://en.wikipedia.org/wiki/Interpolation_search.
(Algoritm haqida umumiy ma'lumot va havolalar)
9. "Interpolation
Search
Algorithm."
GeeksforGeeks,
https://www.geeksforgeeks.org/interpolation-search/. (Algoritmning tushuntirilishi va
implementatsiya misollari)
