Agar yo’q sonni masalan, 23 ni izlab ko’radigan bo’lsak huddi shunday jarayon bo’ladi va natijaviy indeks 9 bo’ladi.
Binar qidiruvning C++ dagi kodi: int binsearch(int x, int left, int right) {
while (right-left > 1) {
int middle = (left+right) / 2;
if (a[middle] > x)
right = middle;
else
left = middle;
}
if (a[left]==x)
return left;
return -1;
}
Dastur asosiy qismida massiv elementlarini o’qitamiz va funksiyaga murojaat qilamiz:
cout<Agar x soni massivda mavjud bo’lsa unda u turgan massiv indeksini, aks holda
-1 sonini chiqaradi.
Massiv elementlari yagona bo’lmaganda binar qidiruv. Kamaymaslik tartibda saralangan massiv berilgan.
Massiv elementlari takrorlanishi mumkin, ya’ni bir son massivda birnecha marta qatnashishi mumkin bo’lsin.
Berilgan elementni qidirish kerak, agar mavjud bo’lsa uning boshlang’ich va oxirgi indekslarini chiqarish kerak.
Masalan:
Avval yozgan funkisiyamiz aynan oxirgi indeksni topadi. Ya’ni 7 soni uchun 9 ni topadi.
Buning uchun funksiya nomini “upperbound”(“yuqori chegara”) deb qo’yish maqsadga muvofiq.
Boshlang’ich indeksni topish uchun nima qilish kerak? Buni mustaql yozib ko’ring.
1-Topshiriq Bir o’lchamli sonli massiv berilgan. Massiv elementlari o’sish tartibida berilgan.
Keyin m ta son beriladi. Bu sonlardan nechtasi berilgan massivda uchrashini topuvchi dasturtuzing.
Kiruvchi ma’lumotlar Birinchi qatorda bitta butun n soni−massiv elementlari soni berilgan(1≤n≤105).
Ikkinchi qatorda n ta
son−massiv elementlari o’sish tartibda bitta probel bilan ajratibberilgan. Uchinchi
qatorda butun m−so’rovlar soni berilgan(1≤m≤105). Keyingi m taqatorda har birida bittadan son−izlanayotgan son berilgan. Massiv elementlari vaizlanayotgan sonlar butun va modul jihatdan 109 dan oshmaydi.
