Ikkilik qidiruv qanday ishlaydi va nega u muhim algoritm hisoblanadi
Ikkilik qidiruv ``monoton'' xatti-harakatga ega bo‘lganda elementni yoki optimal qiymatni samarali topish uchun qo‘llaniladigan fundamental usuldir.
Faraz qilaylik, bizda tartiblangan massiv bor va biz qiymatining pozitsiyasini topmoqchimiz, ya’ni bo‘ladigan indeksni.
Sodda yechim — massivni ko‘zdan kechirish:
Bu vaqt ichida ishlaydi.
Biroq, massiv tartiblanganligi sababli, biz ancha yaxshiroq qila olamiz: ikkilik qidiruvdan foydalanib vaqtga erishamiz: biz javobni (agar u mavjud bo‘lsa) albatta o‘z ichiga oladigan oraliqni saqlaymiz, uni qayta-qayta ikki yarmga bo‘lamiz va javob bo‘lishi mumkin bo‘lmagan yarmini tashlab yuboramiz.
Endi bo‘ladigan istalgan indeksni qaytaradigan, yoki mavjud bo‘lmasa qaytaradigan standart iterativ ikkilik qidiruvni tasvirlaymiz.
Javob oralig‘ini, ya’ni javob yotadigan intervalni () boshlang‘ich holatga keltiring. Eng boshida, .
So‘ng bizda ikki holat bor:
int find_linear(int x) {
for (int i = 1; i <= n; i++) {
if (a[i] == x) {
return i;
}
}
return -1; // agar x massivda mavjud bo'lmasa
}
int binary_search_any(int x) {
int l = 1;
int r = n;
while (l < r) {
int m = (l + r) / 2;
if (a[m] < x) {
l = m + 1;
} else {
r = m;
}
}
if (a[l] == x) {
return l;
}
return -1;
}