লিনিয়ার সার্চ এবং বাইনারি সার্চ

সার্চিং অ্যালগরিদম (Searching Algorithms) - ডাটা স্ট্রাকচার & অ্যালগরিদম (Data Structure & Algorithms) - Computer Science

340

লিনিয়ার সার্চ (Linear Search)

লিনিয়ার সার্চ হলো একটি সরল সার্চিং অ্যালগরিদম, যেখানে তালিকার প্রতিটি উপাদান একে একে পরীক্ষা করে লক্ষ্য মানটি খুঁজে বের করা হয়। এটি অর্ডারড এবং আনঅর্ডারড উভয় ধরনের তালিকার জন্য কাজ করে।

কাজ করার পদ্ধতি:

প্রথম উপাদান থেকে শুরু করে প্রতিটি উপাদান লক্ষ্য মানের সাথে তুলনা করা হয়।
যদি মানটি পাওয়া যায়, তাহলে ইনডেক্স ফেরত দেওয়া হয়।
যদি শেষ উপাদান পর্যন্ত মানটি না পাওয়া যায়, তাহলে "মানটি নেই" নির্দেশ করা হয়।

টাইম কমপ্লেক্সিটি:

সর্বোচ্চ (Worst Case): O(n)
সর্বনিম্ন (Best Case): O(1)

উদাহরণ (Python):

def linear_search(arr, target):
    for index in range(len(arr)):
        if arr[index] == target:
            return index  # লক্ষ্য মানের ইনডেক্স
    return -1  # লক্ষ্য মান না পেলে -1

# ব্যবহার উদাহরণ
arr = [4, 2, 3, 5, 1]
target = 3
result = linear_search(arr, target)
print(result)  # আউটপুট: 2

বাইনারি সার্চ (Binary Search)

বাইনারি সার্চ হলো একটি দ্রুত সার্চিং অ্যালগরিদম, যা কেবলমাত্র সাজানো তালিকা (Ordered List)-এ কাজ করে। এটি প্রতিবার তালিকাটিকে দুইভাগে ভাগ করে মধ্যবর্তী উপাদানের সাথে লক্ষ্য মানের তুলনা করে।

কাজ করার পদ্ধতি:

প্রথমে তালিকার মাঝখানের উপাদান চিহ্নিত করা হয়।
যদি মাঝখানের উপাদান লক্ষ্য মানের সমান হয়, তাহলে ইনডেক্স ফেরত দেওয়া হয়।
যদি লক্ষ্য মানটি ছোট হয়, তাহলে বাম দিকের অংশে পুনরাবৃত্তি করা হয়।
যদি লক্ষ্য মানটি বড় হয়, তাহলে ডান দিকের অংশে পুনরাবৃত্তি করা হয়।
যদি শেষ পর্যন্ত মানটি না পাওয়া যায়, তাহলে "মানটি নেই" নির্দেশ করা হয়।

টাইম কমপ্লেক্সিটি:

সর্বোচ্চ (Worst Case): O(log n)
সর্বনিম্ন (Best Case): O(1)

উদাহরণ (Python):

def binary_search(arr, target):
    left, right = 0, len(arr) - 1  # শুরু এবং শেষ ইনডেক্স নির্ধারণ
    while left <= right:
        mid = (left + right) // 2  # মাঝখানের ইনডেক্স
        if arr[mid] == target:
            return mid  # লক্ষ্য মানের ইনডেক্স
        elif arr[mid] < target:
            left = mid + 1  # ডান অংশে অনুসন্ধান
        else:
            right = mid - 1  # বাম অংশে অনুসন্ধান
    return -1  # লক্ষ্য মান না পেলে -1

# ব্যবহার উদাহরণ
arr = [1, 2, 3, 4, 5]  # সাজানো তালিকা
target = 3
result = binary_search(arr, target)
print(result)  # আউটপুট: 2