সার্চিং এলগরিদম (Searching Algorithms in C)

Searching Algorithms হল বিভিন্ন কৌশল যা ডেটার মধ্যে একটি নির্দিষ্ট উপাদান খুঁজে বের করতে ব্যবহৃত হয়। সাধারণত দুই ধরনের সার্চিং এলগরিদম ব্যবহৃত হয়: Linear Search এবং Binary Search।

সার্চিং এলগরিদমের তুলনা

৪. উপসংহার

Searching Algorithms হল গুরুত্বপূর্ণ কৌশল যা বিভিন্ন ডেটার মধ্যে উপাদান খুঁজে বের করতে ব্যবহৃত হয়। Linear Search সহজ কিন্তু ধীর, যেখানে Binary Search দ্রুত এবং কার্যকরী, তবে এটি শুধুমাত্র সন্নিবেশিত তালিকার উপর কাজ করে। উভয় পদ্ধতি বিভিন্ন পরিস্থিতিতে ব্যবহৃত হয়, এবং তাদের সুবিধা ও অসুবিধাগুলি বুঝে, সঠিকভাবে ব্যবহৃত হলে ডেটা পরিচালনার জন্য কার্যকরী হতে পারে।

Linear Search হল একটি সহজ এবং মৌলিক সার্চিং পদ্ধতি যা একটি তালিকার প্রতিটি উপাদানকে একে একে পরীক্ষা করে। যখন একটি লক্ষ্য উপাদান পাওয়া যায়, তখন তার ইনডেক্স ফেরত দেয়। যদি উপাদানটি তালিকায় না পাওয়া যায়, তবে এটি সাধারণত -1 ফেরত দেয়।

Linear Search এর কাজের পদ্ধতি:

1. প্রথমে তালিকার প্রথম উপাদান পরীক্ষা করা হয়।
2. যদি প্রথম উপাদানটি লক্ষ্য উপাদানের সমান হয়, তাহলে সেই ইনডেক্স ফেরত দেওয়া হয়।
3. যদি নয়, তবে পরবর্তী উপাদানে যাওয়া হয় এবং পুনরাবৃত্তি করা হয়।
4. এটি শেষ উপাদান পর্যন্ত চলতে থাকে যতক্ষণ না লক্ষ্য উপাদান পাওয়া যায় অথবা তালিকার শেষ না হয়।

Linear Search এর গঠন

#include <stdio.h>

// Function to perform linear search
int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // Return index if target is found
        }
    }
    return -1; // Return -1 if target is not found
}

int main() {
    int arr[] = {10, 20, 30, 40, 50}; // Example array
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 30; // Element to search for

    int result = linearSearch(arr, size, target);
    if (result != -1) {
        printf("Element found at index %d\n", result);
    } else {
        printf("Element not found\n");
    }

    return 0;
}

১. কোড বিশ্লেষণ

linearSearch ফাংশন:

• ইনপুট হিসেবে একটি অ্যারে, এর সাইজ এবং লক্ষ্য উপাদান গ্রহণ করে।
• একটি লুপের মাধ্যমে প্রতিটি উপাদান পরীক্ষা করে।
• যদি লক্ষ্য উপাদান পাওয়া যায়, তবে ইনডেক্স ফেরত দেয়।
• না হলে, -1 ফেরত দেয়।

main ফাংশন:

• একটি উদাহরণ অ্যারে তৈরি করে এবং একটি লক্ষ্য উপাদান নির্ধারণ করে।
• linearSearch ফাংশন কল করে এবং ফলাফল প্রিন্ট করে।

২. Linear Search এর সময় জটিলতা

• Worst Case: O(n) - যদি লক্ষ্য উপাদান তালিকার শেষ উপাদান হয় বা তালিকায় না থাকে।
• Best Case: O(1) - যদি লক্ষ্য উপাদান তালিকার প্রথম উপাদান হয়।
• Average Case: O(n) - গড় ক্ষেত্রে, এটি প্রায় অর্ধেক উপাদান পরীক্ষা করতে হয়।

Binary Search একটি দ্রুত সার্চিং পদ্ধতি যা শুধুমাত্র সন্নিবেশিত (sorted) তালিকার উপর কাজ করে। এটি তালিকাকে পুনরায় বিভক্ত করে লক্ষ্য উপাদানটি খুঁজে বের করে, এবং এর সময় জটিলতা O(log n)।

Binary Search এর কাজের পদ্ধতি:

1. তালিকার মধ্যবর্তী উপাদান নির্ধারণ করুন।
2. লক্ষ্য উপাদানটি মধ্যবর্তী উপাদানের থেকে ছোট হলে বাম দিকের অংশে অনুসন্ধান করুন, আর বড় হলে ডান দিকের অংশে অনুসন্ধান করুন।
3. এই প্রক্রিয়াটি তখন পর্যন্ত চলতে থাকে যতক্ষণ না লক্ষ্য উপাদান পাওয়া যায় বা তালিকার অংশটি খালি হয়ে যায়।

Binary Search এর গঠন

#include <stdio.h>

// Function to perform binary search
int binarySearch(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

        // Check if the target is present at mid
        if (arr[mid] == target) {
            return mid; // Return index if target is found
        }
        // If target is greater, ignore left half
        if (arr[mid] < target) {
            left = mid + 1;
        } 
        // If target is smaller, ignore right half
        else {
            right = mid - 1;
        }
    }
    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 = binarySearch(arr, size, target);
    if (result != -1) {
        printf("Element found at index %d\n", result);
    } else {
        printf("Element not found\n");
    }

    return 0;
}

১. কোড বিশ্লেষণ

binarySearch ফাংশন:

• ইনপুট হিসেবে একটি সন্নিবেশিত অ্যারে, এর সাইজ এবং লক্ষ্য উপাদান গ্রহণ করে।
• দুইটি সূচক left এবং right দিয়ে শুরু হয়।
• একটি লুপের মাধ্যমে মধ্যবর্তী উপাদান খুঁজে বের করে এবং লক্ষ্য উপাদানের সাথে তুলনা করে।
• যদি লক্ষ্য উপাদান পাওয়া যায়, তবে ইনডেক্স ফেরত দেয়।
• যদি লক্ষ্য উপাদান মধ্যবর্তী উপাদানের থেকে ছোট হয়, তবে left আপডেট করা হয়। অন্যথায়, right আপডেট করা হয়।
• যদি লক্ষ্য উপাদান না পাওয়া যায়, তাহলে -1 ফেরত দেয়।

main ফাংশন:

• একটি সন্নিবেশিত উদাহরণ অ্যারে তৈরি করে এবং একটি লক্ষ্য উপাদান নির্ধারণ করে।
• binarySearch ফাংশন কল করে এবং ফলাফল প্রিন্ট করে।

২. Binary Search এর সময় জটিলতা

• Worst Case: O(log n) - যখন সবচেয়ে কম সংখ্যক পরিদর্শন করা হয়।
• Best Case: O(1) - যদি লক্ষ্য উপাদান মধ্যবর্তী উপাদান হয়।
• Average Case: O(log n) - গড় ক্ষেত্রে।

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 এর তুলনা

Time Complexity হল একটি পরিমাপ যা একটি অ্যালগরিদমের কার্যকারিতা বোঝায়, অর্থাৎ, এটি কত দ্রুত বা ধীরগতিতে কাজ করবে। সার্চিং অ্যালগরিদমগুলির জন্য, সময় জটিলতা সাধারণত ইনপুটের আকারের সাথে সম্পর্কিত হয়। নিচে বিভিন্ন সার্চিং অ্যালগরিদমের সময় জটিলতা আলোচনা করা হলো।

১. Linear Search

Linear Search একটি সহজ এবং মৌলিক সার্চিং পদ্ধতি। এটি প্রতিটি উপাদানকে একে একে পরীক্ষা করে লক্ষ্য উপাদানটি খুঁজে বের করে।

Worst Case Time Complexity: O(n)
(যখন লক্ষ্য উপাদান তালিকার শেষ উপাদান হয় বা তালিকায় না থাকে।)

Best Case Time Complexity: O(1)
(যখন লক্ষ্য উপাদান তালিকার প্রথম উপাদান হয়।)

Average Case Time Complexity: O(n)
(গড় ক্ষেত্রে, এটি প্রায় অর্ধেক উপাদান পরীক্ষা করতে হয়।)

২. Binary Search

Binary Search একটি দ্রুত সার্চিং পদ্ধতি যা শুধুমাত্র সন্নিবেশিত (sorted) তালিকার উপর কাজ করে। এটি তালিকাকে পুনরায় বিভক্ত করে লক্ষ্য উপাদানটি খুঁজে বের করে।

Worst Case Time Complexity: O(log n)
(তালিকার মধ্যে লক্ষ্য উপাদানটি না পাওয়া গেলে বা যদি এটি শেষের দিকে থাকে।)

Best Case Time Complexity: O(1)
(যখন লক্ষ্য উপাদান মধ্যবর্তী উপাদান হয়।)

Average Case Time Complexity: O(log n)
(গড় ক্ষেত্রে, এটি প্রায় অর্ধেক উপাদান পরীক্ষা করতে হয়।)

৩. সার্চিং এলগরিদমের সময় জটিলতার তুলনা

৪. সময় জটিলতার মূলনীতি

1. O(1): সময়ের পরিমাণ ইনপুটের আকারের উপর নির্ভর করে না। (Constant time)
2. O(n): সময়ের পরিমাণ ইনপুটের আকারের সাথে সরাসরি অনুপাতিত। (Linear time)
3. O(log n): সময়ের পরিমাণ ইনপুটের আকারের লগারিদমিকভাবে বৃদ্ধি পায়। (Logarithmic time)
4. O(n^2): সময়ের পরিমাণ ইনপুটের আকারের বর্গ। (Quadratic time)

৫. উপসংহার

Searching Algorithms এর সময় জটিলতা বোঝা প্রোগ্রামিংয়ের জন্য খুবই গুরুত্বপূর্ণ, কারণ এটি একটি অ্যালগরিদমের কার্যকারিতা নির্ধারণ করে। Linear Search এবং Binary Search এর মধ্যে প্রধান পার্থক্য তাদের সময় জটিলতা, যেখানে Binary Search অনেক দ্রুত এবং কার্যকরী। বিভিন্ন পরিস্থিতিতে সঠিক অ্যালগরিদম নির্বাচন করা আপনার প্রোগ্রামের কার্যকারিতা বাড়ায়।