Ishdan maqsad: Talabalarda "Bo’lib tashla va hukmronlik qil" tamoyilidagi algoritmlarni asimptotik tahlil qilish bo’yicha ko’nikmalar hosil qilish

Download 0,53 Mb.
bet	4/4
Sana	18.05.2024
Hajmi	0,53 Mb.
	#241454

1 2 3 4

Bog'liq
Al3

int binarqidiruv(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
// Agar element x ga teng bo'lsa
// o'zi qaytadi
if (arr[mid] == x)
return mid;
// Agar element x dan katta bo'lsa,
// u faqat chap qismni oladi
if (arr[mid] > x)
return binarqidiruv(arr, l, mid-1, x);
// Yoki u faqat o'ng qismni oladi
return binarqidiruv(arr, mid+1, r, x);
}
// Bu yerga yetib keladi, qachonki
// x soni massiv ichidan topilmasa
return -1;
}
int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
//massiv ni elementlar sonini topib olayabmiz
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int natija = binarqidiruv(arr, 0, n-1, x);
(natija == -1)? printf("X soni massivni ichidan topilmadi.")
: printf("X soni massivning %d - elementi.",
natija);
return 0;
}
Dastur ishlaganda " X soni massivning 3 - elementi." degan yozuvni qaytaradi. Sababi massiv elementlari 0 dan boshlanadi.

Topshiriq variantlari:

Dastur uchun yozilgan kod:

#include

#include
using namespace std;

pair binarySearch(const vector& arr, int key) {

int left = 0;
int right = arr.size() - 1;
int comparisons = 0;

while (left <= right) {

int mid = left + (right - left) / 2;
comparisons++;

if (arr[mid] == key) {

return {mid, comparisons};
}
else if (arr[mid] < key) {
left = mid + 1;
}
else {
right = mid - 1;
}
}

return {-1, comparisons}; // Element not found

}

int main() {

vector arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int key;
cout << "Qidirilayotgan kalitni kiriting: ";
cin >> key;

pair result = binarySearch(arr, key);

if (result.first != -1) {
cout << "Kalit topildi indeksda: " << result.first << endl;
} else {
cout << "Kalit topilmadi" << endl;
}
cout << "Solishtirishlar soni: " << result.second << endl;