1-1kidt-21-guruh talabasi Mamatov Otamurodning

Binar qidiruv algoritmi o'nlik, ikkilik yoki boshqa sonlar ustida ishlaydi. Ushbu algoritmni amalga oshirish uchun, ro'yxat saralgan bo'lishi kerak. Bunday holatda, birinchi qadamda ro'yxatni saralash kerak bo'ladi.

Quyidagi kodda, C++ tilida binar qidiruv algoritmi ko'rsatilgan:

#include
using namespace std;

int binarySearch(int arr[], int n, int x) {

int left = 0;
int right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == x) {
return mid;
}
if (arr[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}

int main() {

int arr[] = {2, 5, 10, 13, 18, 20};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 13;
int result = binarySearch(arr, n, x);
if (result == -1) {
cout << "Element topilmadi" << endl;
} else {
cout << "Element indeksi: " << result << endl;
}
return 0;
}

Bu kodda, "binarySearch" funksiyasi ro'yxat, ro'yxat uzunligi va qidirayotgan elementni qabul qiladi. Algoritmda ro'yxatni saralash kerak, shuning uchun "arr" ro'yxatida elementlar kichikdan katta saralgan. Dasturda "n" o'zgaruvchisi ro'yxat uzunligini saqlaydi. "x" o'zgaruvchisi esa qidirayotgan elementni anglatadi.

Funksiyada, qidirayotgan elementni o'rtasiga qo'yilgan "mid" indeksi hisoblanadi. Agar ro'yxatdagi "mid" element qidirayotgan elementga teng bo'lsa, "mid" indeksi qaytariladi. Agar "mid" element qidirayotgan elementdan kichik bo'lsa, qidirayotgan elementni o'rtasidan o'ng tomoniga ko'chirib yuboriladi. Aks holda, qidirayotgan elementni o'rtasidan chap tomoniga ko'chirib yuboriladi.

Keyingi qadamda, funksiya "result" o'zgaruvchisida qidirayotgan elementning indeksi saqlanadi. Agar qidirayotgan element topilmagan bo'lsa, "result" o'zgaruvchisiga "-1" qiymati tayinlanadi. Natijada, "if" va "else" operatorlari yordamida, natija ekranga chiqariladi.

"Hello Uzbekistan" so'zining h harfini binar qidiruv tizimi yordamida topish uchun quyidagi kodni ishlatishingiz mumkin:

#include

#include

using namespace std;

int main() {
string s = "Hello Uzbekistan";
int n = s.size();
sort(s.begin(), s.end()); // ro'yxatni saralash
int l = 0, r = n-1, mid;
while (l <= r) {
mid = (l + r) / 2;
if (s[mid] == 'h') {
cout << "h harfi indeksi: " << mid << endl;
break;
}
else if (s[mid] < 'h')
l = mid + 1;
else
r = mid - 1;
}
return 0;
}

Ushbu kodda, "Hello Uzbekistan" so'zi ro'yxatga saqlanadi va ro'yxat saralandi. Keyin, binar qidiruv algoritmi yordamida 'h' harfi qidiriladi. Harf topilganda, shu harfning indeksi konsolga chiqariladi. Agar 'h' harfi ro'yxatda topilmagan bo'lsa, yuqorida ko'rsatilgan binar qidiruv algoritmlaridan biri ishlatilishi mumkin.

#include
#include
using namespace std;
int main() {
int a[] = {2, 4, 3, 1, 6};
int b[] = {7, 6, 5, 4, 3};
int c[] = {1, 2, 3, 4, 5, 6};
int n = sizeof(a) / sizeof(a[0]);
sort(c, c + 6); // c ro'yxatini saralas
int l = 0, r = n-1, mid;
while (l <= r) {
mid = (l + r) / 2;
if (c[mid] == a[mid] + b[n-mid-1]) {
cout << "a va b ro'yxatlari " << mid+1 << "-chi elementdan ajratilgan holda tartiblangan" << end
break;
}
else if (c[mid] < a[mid] + b[n-mid-1])
l = mid + 1;
else
r = mid - 1;
}
return 0;
}

Ushbu kodda, berilgan ro'yxatlardan a va b ro'yxatlari yig'indisini c ro'yxati deb qabul qilamiz. Keyin, c ro'yxatini saralaymiz. Binar qidiruv algoritmi yordamida, a va b ro'yxatlari ajratilgan holda tartiblangan to'plamni topishga harakat qilamiz. Topilganda, tartiblangan indeks konsolga chiqariladi.

Agar a va b ro'yxatlari ajratilgan holda tartiblangan to'plam topilmagan bo'lsa, yuqorida ko'rsatilgan binar qidiruv algoritmlaridan biri ishlatilishi mumkin.

#include

#include
using namespace std;

int binary_search(int arr[], int n, int x) {

int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] < x) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}

int main() {

int a[] = {9, 8, 7, 6, 5};
int b[] = {3, 4, 5, 6, 7};
int c[] = {4, 7, 2, 5, 6};
int n = sizeof(c) / sizeof(c[0]);
sort(c, c + n);
int index_a = binary_search(c, n, a[0]);
int index_b = binary_search(c, n, b[0]);
cout << "a to'plamidagi eng kichik element tartibida " << index_a << " indeksda joylashgan." << endl;
cout << "b to'plamidagi eng kichik element tartibida " << index_b << " indeksda joylashgan." << endl;
return 0;
}

Bu kodda, binary_search funksiyasi ro'yxat, ro'yxat uzunligi va qidirilayotgan elementni qabul qiladi. Ushbu funksiya binar qidiruv algoritmini ishlatadi va qidirilayotgan elementni topganda, indeksni qaytaradi. Agar element topilmagan bo'lsa, -1 qiymatini qaytaradi.

main funksiyasida, a, b va c ro'yxatlari berilgan. n o'zgaruvchisi c ro'yxati uzunligini saqlaydi. c ro'yxatini sort funksiyasi orqali tartiblash kerak. binary_search funksiyasi yordamida, a va b ro'yxatidagi eng kichik elementlar c ro'yxatida qayerda joylashganligi aniqlanadi va natijada indekslar chiqariladi.

Natijada, programma a va b ro'yxatidagi eng kichik elementlarning tartibida joylashgan indekslarini chiqaradi.

#include
#include
using namespace std;

int binary_search(int arr[], int n) {

int low = 0, high = n - 1;
while (low < high) {
int mid = (low + high + 1) / 2;
if (arr[mid] <= arr[high]) {
low = mid;
} else {
high = mid - 1;
}
}
return arr[high];
}

int main() {

int A[] = {2, 3, 6, 8, 9};
int n = sizeof(A) / sizeof(A[0]);
int max_element = binary_search(A, n);
cout << "Eng katta element: " << max_element << endl;
return 0;
}

binary_search funksiyasi, ro'yxatni va ro'yxat uzunligini qabul qiladi. Ushbu funksiya binar qidiruv algoritmini ishlatadi va ro'yxatdagi eng katta elementni topadi.

main funksiyasida, A ro'yxati berilgan va n o'zgaruvchisi ro'yxat uzunligini saqlaydi. binary_search funksiyasi yordamida, A ro'yxatidagi eng katta element aniqlanadi. Natijada, dastur eng katta elementni chiqaradi.
#include
#include
using namespace std;

int binary_search(int arr[], int n) {

int low = 0, high = n - 1;
while (low < high) {
int mid = (low + high) / 2;
if (arr[mid] >= arr[low]) {
low = mid + 1;
} else {
high = mid;
}
}
return arr[low];
}

int main() {

int A[] = {2, 3, 6, 8, 9};
int n = sizeof(A) / sizeof(A[0]);
int min_element = binary_search(A, n);
cout << "Eng kichik element: " << min_element << endl;
return 0;
}

A = [2,3,6,8,9] berilgan ro'yxatdagi elementlar sonini toping

#include
#include
using namespace std;

int main() {

int A[] = {2, 3, 6, 8, 9};
int n = sizeof(A) / sizeof(A[0]);
int min = A[0];
int max = A[n-1];
cout << "Minimum element: " << min << endl;
cout << "Maximum element: " << max << endl;
return 0;
}

Quyidagi kod C++ dasturlash tilida berilgan A=26 va B=20 sonlarining o'rta qiymatini topadi (binar qidiruv algoritmi orqali):

#include
using namespace std;

double findMid(double a, double b) {

return (a + b) / 2.0;
}

double findAverage(double a, double b) {

double mid = findMid(a, b);
return mid;
}

int main() {

double A = 26;
double B = 20;
double mid = findAverage(A, B);
cout << "The average of " << A << " and " << B << " is " << mid << endl;
return 0;
}

double findMid(double a, double b) funksiyasi 2 ta sonning o'rta qiymatini topish uchun ishlatiladi.

double findAverage(double a, double b) funksiyasi esa findMid funksiyasidan foydalanib, 2 ta sonning o'rta qiymatini topadi.

double A = 26; va double B = 20; qiymatlar beriladi.

double mid = findAverage(A, B); findAverage funksiyasi yordamida A va B o'rtasidagi qiymat topiladi va mid o'zgaruvchiga saqlanadi.

cout << "The average of " << A << " and " << B << " is " << mid << endl; o'rta qiymat chiqariladi.

Natijada, kod A=26 va B=20 sonlari uchun o'rta qiymatni hisoblaydi va konsolga chiqaradi.