Binary Search একটি দ্রুত সার্চিং পদ্ধতি যা সন্নিবেশিত (sorted) তালিকার উপর কাজ করে। এটি মূলত দুটি উপায়ে বাস্তবায়িত হয়: Recursive এবং Iterative। নিচে উভয় পদ্ধতির বিস্তারিত আলোচনা এবং C প্রোগ্রামে উদাহরণ দেওয়া হলো।
১. Recursive Binary Search
১.১ Recursive Binary Search এর ধারণা
Recursive Binary Search হল এমন একটি পদ্ধতি যেখানে একটি ফাংশন নিজেকে কল করে। এটি তালিকার মাঝের উপাদানকে পরীক্ষা করে এবং লক্ষ্য উপাদানটির অবস্থান খুঁজে বের করতে চেষ্টা করে। যদি লক্ষ্য উপাদানটি না পাওয়া যায়, তবে বাম বা ডান দিকের সাব-অ্যারেতে পুনরায় কল করে।
১.২ C প্রোগ্রামে Recursive Binary Search উদাহরণ
#include <stdio.h>
// Recursive function for binary search
int recursiveBinarySearch(int arr[], int left, int right, int target) {
if (left > right) {
return -1; // Base case: target not found
}
int mid = left + (right - left) / 2; // Find the middle index
if (arr[mid] == target) {
return mid; // Return index if target is found
} else if (arr[mid] < target) {
return recursiveBinarySearch(arr, mid + 1, right, target); // Search in right half
} else {
return recursiveBinarySearch(arr, left, mid - 1, target); // Search in left half
}
}
int main() {
int arr[] = {10, 20, 30, 40, 50}; // Sorted array
int size = sizeof(arr) / sizeof(arr[0]);
int target = 30; // Element to search for
int result = recursiveBinarySearch(arr, 0, size - 1, target);
if (result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found\n");
}
return 0;
}
২. Iterative Binary Search
২.১ Iterative Binary Search এর ধারণা
Iterative Binary Search হল একটি পদ্ধতি যেখানে একটি লুপের মাধ্যমে লক্ষ্য উপাদানটি খোঁজা হয়। এখানে কোন পুনরাবৃত্তি নেই, বরং লুপ ব্যবহার করে উপাদানগুলি পরীক্ষা করা হয়।
২.২ C প্রোগ্রামে Iterative Binary Search উদাহরণ
#include <stdio.h>
// Iterative function for binary search
int iterativeBinarySearch(int arr[], int size, int target) {
int left = 0;
int right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Find the middle index
if (arr[mid] == target) {
return mid; // Return index if target is found
}
if (arr[mid] < target) {
left = mid + 1; // Search in the right half
} else {
right = mid - 1; // Search in the left half
}
}
return -1; // Return -1 if target is not found
}
int main() {
int arr[] = {10, 20, 30, 40, 50}; // Sorted array
int size = sizeof(arr) / sizeof(arr[0]);
int target = 30; // Element to search for
int result = iterativeBinarySearch(arr, size, target);
if (result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found\n");
}
return 0;
}
৩. Recursive এবং Iterative Binary Search এর তুলনা
| বৈশিষ্ট্য | Recursive Binary Search | Iterative Binary Search |
|---|---|---|
| কোডের পরিষ্কারতা | সাধারণত কোড পরিষ্কার এবং সহজ | কোড কিছুটা জটিল হতে পারে |
| স্ট্যাক ব্যবহার | স্ট্যাক ফ্রেম ব্যবহার করে; স্ট্যাক ওভারফ্লোর ঝুঁকি থাকে | স্ট্যাক ব্যবহার করে না |
| পারফরম্যান্স | কিছুক্ষেত্রে কম কার্যকরী হতে পারে | সাধারণত দ্রুত এবং কম মেমরি ব্যবহার করে |
| বেস কেস | বেস কেসের প্রয়োজন | কোন বেস কেসের প্রয়োজন নেই |
Content added By
Read more
