Haqiqiy ikkilik qidiruv
![Ikkilik qidiruvning ishlashini Lug'at misoli bilan bog'lashingiz mumkin.
Faraz qilaylik, bizning vazifamiz so'zining ma'nosini topishdir. Lug'atda so'zlar
alifbo tartibida joylashtirilgan.
Bir yondashuv lug'atdagi har bir so'zni maqsadli so'z bilan (chiziqli
qidiruv) o'qish va solishtirishdir. Biroq, siz sezganingizdek, bu usul ko'p vaqt
talab etadi, chunki siz butun lug'atni skanerlashingiz kerak.
Yaxshiroq yondashuv bormi? Ha, biz yuqorida aytib o'tilganidek, ikkilik
qidiruvdan foydalanishimiz mumkin.
Lug'atning o'rta sahifasini ochib, o'rta sahifadagi so'zlarni xotirjamlik bilan
solishtirishimiz mumkin. Tinchlik so'zi alifbo tartibida o'rta sahifadagi so'zlardan
keyin kelsa, biz lug'atning chap tomoniga e'tibor bermaymiz. Aks holda,
lug'atning chap tomoniga e'tibor bermaymiz.
Tinchlik so'zini topgunimizcha bu jarayonni davom ettiramiz. Lug‘atlar
soni n ta bo’lsa, biz Tinchlik so‘zini eng yomon holatda log
2 (n) iteratsiyada topa
olamiz.
Biz ikkilik qidiruvi orqali boshqa qidiruv algoritmlariga qaraganda vaqtdan ham,
xotiradan ham yutamiz.
1.2 Ikkilik qidiruvning psevdokodi
Ikkilik qidiruvning ishlashini muhokama qilganimizdan so'ng, keling,
uning psevdokodi qanday ko'rinishini ko'rib chiqaylik:
Start binary_search
arr ← init or input a sorted array
size ← size of the array
k ← value to be searched
Initialize start = 0
Initialize end = size - 1
Repeat while start <= end
set mid = (start + end) / 2
if arr[mid] == k
RETURN: k found at location mid, return mid
else if arr[mid] > k
set end = mid - 1
else if arr[mid] < k
5](/data/documents/ae10a9cc-4e36-4717-af3c-92cf9785d605/page_5.png)
![function meta_binary_search(A, target):
n = length(A)
interval_size = n
while interval_size > 0:
index = min(n - 1, interval_size / 2)
mid = A[index]
if mid == target:
return index
elif mid < target:
interval_size = (n - index) / 2
else:
interval_size = index / 2
return -1
2.2 Sentinel ikkilik qidiruv
Nomidan ko'rinib turibdiki, Sentinel ikkilik qidiruv bu chiziqli qidiruvning
bir turi bo'lib, an'anaviy chiziqli qidiruvga nisbatan taqqoslashlar soni kamayadi.
N o'lchamdagi massivda chiziqli qidiruv amalga oshirilganda, eng yomon
holatda, qidirilayotgan element massivning barcha elementlari bilan
taqqoslaganda jami N ta taqqoslash amalga oshiriladi va (2N + 1) taqqoslash
amalga oshiriladi. Indeks Sentinel chiziqli qidiruv qisqartirilishi mumkin bo'lgan
massiv chegaralaridan tashqarida bo'lmasligi uchun solishtiriladigan element
indeksi.
Bu qidiruvda massivning oxirgi elementi izlanadigan element bilan
almashtiriladi, so‘ngra joriy indeks massivning indeks diapazonida yoki yo‘qligi
tekshirilmasdan, chiziqli izlash massivda amalga oshiriladi, chunki izlanadigan
element. Oxirgi element u bilan almashtirilgandan beri asl massivda bo'lmasa
ham, albatta massiv ichida topiladi. Shunday qilib, tekshiriladigan indeks hech
qachon massiv chegarasidan tashqariga chiqmaydi. Eng yomon holatda
taqqoslashlar soni (N + 2) bo'ladi.
Sentinel chiziqli qidiruv - massiv yoki ro'yxatdagi maqsadli qiymatni
topish uchun ishlatiladigan standart chiziqli qidiruv algoritmining o'zgarishi.
Ushbu algoritmning asosiy g'oyasi massivning oxiriga biz izlayotgan maqsadli
8](/data/documents/ae10a9cc-4e36-4717-af3c-92cf9785d605/page_8.png)
![qiymatga teng bo'lgan sentinel qiymatini qo'shishdir. Bu siklning har bir
iteratsiyasida massiv chegarasi holatini tekshirishdan qochishga yordam beradi,
chunki sentinel qiymati tsikl uchun to'xtatuvchi vazifasini bajaradi.
Garchi eng yomon vaqt murakkabligida ikkala algoritm ham O (n) dir.
Sentinel chiziqli qidiruvda faqat taqqoslashlar soni chiziqli qidiruvga qaraganda
kamroq
Sentinel chiziqli qidiruvidan foydalanish:
Massivdagi elementni qidirish kontekstida Sentinel Linear Search qidiruv
jarayonini optimallashtirish uchun sentinel qiymatidan foydalanadigan chiziqli
qidiruv algoritmining variantidir.
Sentinel chiziqli qidiruv -ning asosiy g'oyasi qidiruv kalitiga mos
keladigan massivning oxiriga qo'shimcha element qo'shishdir (ya'ni, sentinel
qiymati). Shunday qilib, biz sikldagi massiv oxirini shartli tekshirishdan
qochishimiz va qo'riqchi elementni topishimiz bilanoq qidiruvni erta tugatishimiz
mumkin. Bu massivning oxirini alohida tekshirish zaruratini yo'q qiladi, natijada
algoritmning o'rtacha ish ko'rsatkichlari biroz yaxshilanadi.
Sentinel chiziqli qidiruv algoritmi uchun qadamlar:
Qidiruv indeksi o'zgaruvchisini i dan 0 gacha ishga tushiring.
Massivning oxirgi elementini qidirish tugmachasiga o‘rnating.
Qidiruv kaliti massivning joriy elementiga (ya‘ni, arr[i]) teng
bo'lmasa-da, i qidiruv indeksini oshiring.
Agar i massiv o‘lchamidan kichik bo'lsa yoki arr[i] qidiruv kalitiga
teng bo'lsa, i qiymatini qaytaring (ya'ni, massivdagi qidiruv kaliti indeksi).
Aks holda, qidiruv kaliti massivda mavjud emas, shuning uchun -1
ni qaytaring (yoki kalit topilmaganligini ko'rsatish uchun boshqa tegishli qiymat).
Sentinel chiziqli qidiruv algoritmining asosiy afzalligi shundaki, u massiv
oxirini alohida tekshirish zaruratini yo'q qiladi, bu esa algoritmning o'rtacha ish
faoliyatini yaxshilashi mumkin. Biroq, u hali ham O(n) bo'lgan eng yomon ish
faoliyatini yaxshilamaydi (bu erda n - massivning o'lchami), chunki sentinel
qiymatini topish uchun biz butun massivni skanerlashimiz kerak bo'lishi mumkin.
Misollar:
input: arr[] = {10, 20, 180, 30, 60, 50, 110, 100, 70}, x = 180
Output: 180 2-indeksda joylashgan
Input: arr[] = {10, 20, 180, 30, 60, 50, 110, 100, 70}, x = 90
9](/data/documents/ae10a9cc-4e36-4717-af3c-92cf9785d605/page_9.png)
![elementlar bir xil taqsimlanmaganda samaraliroq bo ladi.Interpolatsiya qidiruvi ʻ
ikkilik qidiruvga qaraganda ko'proq vaqt talab qilishi mumkin, chunki u maqsadli
elementning o'rnini baholash uchun qo'shimcha hisob-kitoblardan foydalanishni
talab qiladi.
Dastur1:
//high ->yuqori index, low->quyi index, target->maqsadli //element
#include<bits/stdc++.h>
using namespace std;
int interpolation_search(int arr[],int target, int n){
int low = 0;
int high = n - 1;
while (low <= high && target >= arr[low] && target <= arr[high]){
// uning qiymatiga asoslangan maqsadli elementning o‘rnini
aniqlaymiz
int pos = low + (((target - arr[low]) * (high - low)) / (arr[high]
- arr[low]));
// Agar maqsadli element hisoblash o‘rnidagi element bo‘lsa,
o‘zini chiqaramiz
if( arr[pos] == target){
return pos;
}
// Agar hisoblangan holatdagi elementdan maqsadli element
kichik bo‘lsa, ro’yxat yarmining chap qismidan qidiramiz
if(arr[pos] > target){
high = pos - 1;
}
else{
// Agar hisoblangan holatdagi elementdan maqsadli
element katta bo‘lsa, ro’yxat yarmining o‘ng qismidan qidiramiz
low = pos + 1;
12](/data/documents/ae10a9cc-4e36-4717-af3c-92cf9785d605/page_12.png)
![}
}
return -1;
}
int main(){
int arr[] = {3, 5, 7, 9, 11, 13, 17, 19, 23};
int n = sizeof(arr)/sizeof(int);
int target = 5;
int index = interpolation_search(arr, target, n);
// cout << index << endl;
if(index == -1){
cout << target << " ro’yxatda yo’q" << endl;
}
else{
cout << target << " indeksda topildi " << index << endl;
}
}
Interpolatsiya qidiruvi o'rtacha hisobda log(log(n)) taqqoslashni amalga
oshiradi (agar elementlar bir xilda taqsimlangan bo'lsa), bu erda n - izlanadigan
elementlar soni. Eng yomon holatda (masalan, tugmachalarning sonli qiymatlari
eksponent ravishda ortib borsa) u O(n) ga teng taqqoslashlarni amalga oshirishi
mumkin.
2.4 C++ da bsearch() ikkilik qidiruv funksiyasi
C++ tilida bizda stdlib.h sarlavha faylida mavjud bsearch()
o'rnatilgan kutubxona funksiyasi mavjud. U C++ tilida oldindan belgilangan
bo'lib, biz yuqorida muhokama qilganimizdek ishlaydi. bsearch() elementni
saralangan ro'yxat/massivdan tezda qidirish uchun ishlatilishi mumkin.
Funktsiya formati:
#include <iostream>
void *bsearch(const void *key, const void *base, size_t num, size_t size,
13](/data/documents/ae10a9cc-4e36-4717-af3c-92cf9785d605/page_13.png)
![int (*compare)(const void *element1, const void *element2));
Qaytish qiymati : bsearch() qidiruv kalitiga mos keladigan
massiv elementiga ko'rsatgichni qaytaradi. Agar kalit uchun moslik topilmasa,
NULL qiymati qaytariladi.
Dastur://C
#include <iostream>
using namespace std;
int compare(const void * m,const void * n) {
return ( * (int * ) m - * (int * ) n);
}
int main() {
int arr[6] = {1,5,19,26,31,69};
int * element;
int key; // search element
cout << "Enter the target element: ";
cin >> key;
/* bsearch() massivning ichida 31 qiymatini topish uchun ishlatildi*/
element = (int * ) bsearch( & key, arr, 6, sizeof(int), compare);
if (element != NULL)
{
cout << "\n%d is found in the array" << *element;
}
else
{
cout << "\n%d could not be found in the array" << key;
}
return 0;
}
Dasturni takshiramiz va ishga tushiramiz.
14](/data/documents/ae10a9cc-4e36-4717-af3c-92cf9785d605/page_14.png)
Mavzu: “Haqiqiy ikkilik qidiruv” Mundarija I BOB. KIRISH ................................................................................................................................................................................................... 2 1.1 Haqiqiy ikkilik qidiruv nima? ...................................................................................................................................................................... 2 1.2 Ikkilik qidiruvning psevdokodi ................................................................................................................................................................... 5 1.3 Ikkilik qidiruvning afzalliklari ..................................................................................................................................................................... 6 II BOB. C++ tilida ikkilik qidiruv turlari ............................................................................................................................................................. 7 2.2 Sentinel ikkilik qidiruv ............................................................................................................................................................................... 8 2.3 Interpolatsiyali qidiruv va Ikkilik qidiruv .................................................................................................................................................. 11 2.4 C++ da bsearch() ikkilik qidiruv funksiyasi ............................................................................................................................................... 13 III BOB. Binar(Ikkilik) daraxtlar ...................................................................................................................................................................... 16 3.1 Ikkilik daraxtga kirish ............................................................................................................................................................................... 16 3.1.1 Ma'lumotlar tuzilishi va algoritm bo'yicha qo'llanmalar ...................................................................................................................... 16 3.2 Ikkilik daraxt o'tishlari: ............................................................................................................................................................................ 19 XULOSA ........................................................................................................................................................................................................ 22 FOYDALANILGAN ADABIYOTLAR ................................................................................................................................................................... 23
I BOB. KIRISH 1.1 Haqiqiy ikkilik qidiruv nima? Algoritm tushunchasi zamonaviy matematika va informatikaning asosiy tushunchalaridan biri hisoblanadi. Algoritm termini o’rta asrlar ulug’ matematigi al-Xorazmiy nomidan kelib chiqqan. XX asrning 30-yiligacha algoritm tushunchasi ko’proq matematik ma’no emas, balki metodologik ma’noni kasb etar edi. Algoritm deganda, u yoki bu masalalar sinfini yechish imkonini beruvchi aniq ifodalangan chekli qoidalar majmui tushunilgan. EHM larning paydo bo’lishi bilan algoritm tushunchasi yanada keng tarqaldi. EHM va dasturlash usullarining rivojlanishi algoritmlarni ishlab chiqish avtomatlashtirishdagi zaruriy bosqich ekanligini tushunishga yordam berdi. EHM larning paydo bo’lishi algoritmlar nazariyasining rivojlanishiga olib keldi. Algoritmlarni tuzish – bu ijodiy ish bo’lib, ixtiyoriy zaruriy algoritmni tuzish uchun umumiy usullar mavjud emas, kishining ijodiy qobiliyatiga bog’liq. Algoritm tushunchasini formallashtirish asosida ularning samaradorliga taqqoslash, ularning ekvivalentligini tekshirish, qo’llanilish sohasini aniqlash mumkin. 1930 yillarda yaratilgan (Post, Turing, Church) algoritmlarning turli-tuman modellar 1950 yillarda taklif qilingan Kolmogorov va Markovning modelari singari bir xil, ekvivalentlik shu ma’noda-ki, bir modelda echib bo‘ladigan muammolarning har qanday sinfi, boshqasida ham hal etiladi. Hozirgi paytda algoritmlar nazariya asosida olingan amaliy tavsiyanomalar dasturiy tizimlarni loyihalash va ishlab chiqish sohalarida keng tarqalgan. Tezroq qidirish imkonini beradigan narsalar ro'yxatini saralash g'oyasi antik davrga borib taqaladi. Ma‘lum bo'lgan eng qadimgi misol Bobildan eramizgacha bo'lgan Inakibit-Anu planshetidir. Miloddan avvalgi 200 - yil. Planshetda 500 ga yaqin kichik kichik raqamlar va ularning leksikografik tartibda tartiblangan o'zaro raqamlari mavjud bo'lib, bu ma'lum bir yozuvni qidirishni osonlashtirdi. Bundan tashqari, Egey orollarida birinchi harfi bo'yicha saralangan bir nechta nomlar ro'yxati topilgan. Milodiy 1286 - yilda tugallangan lotincha lug'at katolikon so'zlarni faqat birinchi harflardan farqli ravishda alifbo tartibida tartiblash qoidalarini tavsiflovchi birinchi asar edi. 1946-yilda Jon Mauchli birinchi bo lib hisoblash texnikasi bo yicha ʻ ʻ kollejning asosiy kursi bo lgan Mur maktabi ma ruzalarining bir qismi sifatida ʻ ʼ ikkilik qidiruv haqida gapirdi. 1957 yilda Uilyam Uesli Peterson interpolyatsiyani qidirishning birinchi usulini nashr etdi. Har bir nashr etilgan ikkilik qidiruv algoritmi 1960 yilgacha Derrik Genri Lehmer barcha massivlarda ishlaydigan ikkilik qidiruv algoritmini nashr etgunga qadar uzunligi ikki uning kuchidan bir kichik massivlar uchungina ishlagan. 1962 yilda Hermann Bottenbruch ikkilik 2
qidiruvning ALGOL 60 dasturini taqdim etdi, u oxirida tenglik uchun taqqoslashni joylashtirdi, o'rtacha takrorlash sonini bittaga oshirdi, lekin har bir iteratsiyadagi taqqoslash sonini bittaga qisqartirdi. Yagona ikkilik qidiruv 1971 yilda Stenford universitetidan A. K. Chandra tomonidan ishlab chiqilgan. 1986 yilda Bernard Chazelle va Leonidas J. Guibas hisoblash geometriyasida ko'plab qidiruv muammolarini hal qilish usuli sifatida kasr kaskadlarini kiritdilar. Informatika fanida ikkilik qidiruv, shuningdek, yarim intervalli qidiruv, logarifmik qidiruv yoki ikkilik chop deb nomlanuvchi, tartiblangan massiv ichida maqsadli qiymatning o‘rnini topadigan qidiruv algoritmi. Ikkilik qidiruv maqsadli qiymatni massivning o'rta elementi bilan taqqoslaydi. Agar ular teng bo'lmasa, nishon yotolmaydigan yarmi yo'q qilinadi va qolgan yarmida qidirish davom etadi, yana o'rta elementni maqsad qiymat bilan taqqoslash uchun olib, maqsad qiymat topilgunga qadar takrorlanadi. Agar qidiruv qolgan yarmi bo'sh bo'lishi bilan tugasa, maqsad massivda emas. Ikkilik qidiruv logarifmik vaqt ichida eng yomon holatda ishlaydi. Ikkilik qidiruvni qo'llash uchun massiv avval tartiblangan bo'lishi kerak. Tez qidirish uchun mo'ljallangan maxsus ma'lumotlar tuzilmalari mavjud, masalan, xesh- jadvallar, ularni ikkilik qidiruvdan ko'ra samaraliroq qidirish mumkin. Shu bilan birga, ikkilik qidiruv kengroq muammolarni hal qilish uchun ishlatilishi mumkin, masalan, massivda bo'lmasa ham, maqsadga nisbatan massivdagi keyingi eng kichik yoki keyingi eng katta elementni topish. Ikkilik qidiruvning ko'plab variantlari mavjud. Xususan, kasrli kaskad bir nechta massivlarda bir xil qiymat uchun ikkilik qidiruvlarni tezlashtiradi. Fraksiyonel kaskad hisoblash geometriyasi va boshqa ko'plab sohalarda bir qator qidiruv muammolarini samarali hal qiladi. Eksponensial qidiruv ikkilik qidiruvni cheklanmagan ro'yxatlargacha kengaytiradi. Ikkilik qidiruv daraxti va B-daraxt ma'lumotlar tuzilmalari ikkilik qidiruvga asoslangan. Bizda Lineer Search yoki Sequential Search, Binary Search, Jump Search, Fibonachchi Search va boshqalar kabi yana ko'plab qidiruv algoritmlari mavjud va eng samaralilaridan biri Ikkilik qidiruv algoritmidir. Chiziqli qidiruvda biz har bir massiv elementi bilan topilgan elementni massivning boshidan oxirigacha solishtiramiz (massiv elementlarini istalgan tartibda joylashtirish mumkin). Agar massivda maqsadli element topilsa, biz elementning indeksini qaytaramiz, aks holda -1 ni qaytaramiz, bu maqsad element topilmaganligini bildiradi. Elementni topish uchun O(n) vaqt ketadi, ikkilik qidiruv esa faqat O(log 2 N) vaqt oladi. Qanday qilib ko'ramiz. 3
Chiziqli qidiruv tartiblangan massivda Maqsadli element 12 Qidirilgan son 3-indeksda maqsadli 4 6 7 12 23 0 1 2 3 4 indekslar Ko‘rib turganingizdek chiziqli qidiruvda chiziqli qidiruvda ma 7ssiv elementlarini birma-bir tekshirib chiqishimiz kerak.Bu esa katta hajmli ma’lumotlarda kerakli ma’lumotni izlashda bir qancha noqulayliklarga duch kelamiz: 1.Vaqtdan yutqazish; 2.Xotiradan yutqazish. Ikkilik qidiruv algoritmi maqsadli elementni topish uchun tartiblangan massivda ishlaydi va chiziqli qidiruv algoritmiga qaraganda samaraliroq. Shunday qilib, keling, ikkilik qidiruv algoritmi qanday ishlashini ko'rib chiqamiz. Agar sizda izlash kerak bo'lgan massiv bo'lsa, eng oddiy usul indexOf() yoki for() siklidan foydalanish bo'lishi mumkin. Ikkala variant ham massivning chap tomonida boshlanadi va kerakli qiymat topilmaguncha Massivdagi har bir elementni takrorlang. Endi buni Ikkilik qidiruv bilan solishtiramiz. Ikkilik qidiruv massivni qayta-qayta ikkiga bo'lish orqali tartiblangan massivni qidirish imkonini beradi. Ikkilik qidiruv bizning qidiruv qiymatimiz massivdagi o'rta qiymatdan katta , kichik yoki teng ekanligini tekshirish orqali ishlaydi: Agar u kamroq bo'lsa, biz massivning o'ng yarmini olib tashlashimiz mumkin. Agar u ortiq bo'lsa, biz massivning chap yarmini olib tashlashimiz mumkin. Agar u teng bo'lsa, biz qiymatni qaytaramiz Bu yerda diqqatga sazovor narsa shundaki, massiv tartiblangan bo'lishi kerak - ya'ni ikkilik qidiruv ishlashi uchun qiymatlar bo'lishi kerak.Katta ma'lumotlar bo'laklari bilan ishlashda ikkilik qidiruvdan foydalanish tezroq bo'ladi, chunki har bir iteratsiyada bitta noto‘g‘ri qiymat o'rniga massivning noto‘g‘ri qiymatlarining 1/2 qismini olib tashlaysiz. 4
Ikkilik qidiruvning ishlashini Lug'at misoli bilan bog'lashingiz mumkin. Faraz qilaylik, bizning vazifamiz so'zining ma'nosini topishdir. Lug'atda so'zlar alifbo tartibida joylashtirilgan. Bir yondashuv lug'atdagi har bir so'zni maqsadli so'z bilan (chiziqli qidiruv) o'qish va solishtirishdir. Biroq, siz sezganingizdek, bu usul ko'p vaqt talab etadi, chunki siz butun lug'atni skanerlashingiz kerak. Yaxshiroq yondashuv bormi? Ha, biz yuqorida aytib o'tilganidek, ikkilik qidiruvdan foydalanishimiz mumkin. Lug'atning o'rta sahifasini ochib, o'rta sahifadagi so'zlarni xotirjamlik bilan solishtirishimiz mumkin. Tinchlik so'zi alifbo tartibida o'rta sahifadagi so'zlardan keyin kelsa, biz lug'atning chap tomoniga e'tibor bermaymiz. Aks holda, lug'atning chap tomoniga e'tibor bermaymiz. Tinchlik so'zini topgunimizcha bu jarayonni davom ettiramiz. Lug‘atlar soni n ta bo’lsa, biz Tinchlik so‘zini eng yomon holatda log 2 (n) iteratsiyada topa olamiz. Biz ikkilik qidiruvi orqali boshqa qidiruv algoritmlariga qaraganda vaqtdan ham, xotiradan ham yutamiz. 1.2 Ikkilik qidiruvning psevdokodi Ikkilik qidiruvning ishlashini muhokama qilganimizdan so'ng, keling, uning psevdokodi qanday ko'rinishini ko'rib chiqaylik: Start binary_search arr ← init or input a sorted array size ← size of the array k ← value to be searched Initialize start = 0 Initialize end = size - 1 Repeat while start <= end set mid = (start + end) / 2 if arr[mid] == k RETURN: k found at location mid, return mid else if arr[mid] > k set end = mid - 1 else if arr[mid] < k 5