লিনিয়ার সার্চ এবং বাইনারি সার্চ দুটি জনপ্রিয় সার্চিং অ্যালগরিদম। প্রতিটির কাজ হল নির্দিষ্ট একটি উপাদান (এলিমেন্ট) খুঁজে বের করা, তবে তাদের কাজের পদ্ধতি এবং কার্যক্ষমতা ভিন্ন।
লিনিয়ার সার্চ (Linear Search)
লিনিয়ার সার্চ একটি সোজাসাপ্টা সার্চিং অ্যালগরিদম যা একটি ডেটা তালিকায় উপাদান খোঁজার জন্য ক্রমান্বয়ে প্রতিটি উপাদান চেক করে। এটি অবিন্যস্ত এবং বিন্যস্ত উভয় ধরনের তালিকার জন্য কাজ করে।
অ্যালগরিদমের প্রক্রিয়া:
- প্রথম থেকে শুরু করে প্রতিটি উপাদান চেক করতে থাকে।
- যদি উপাদানটি পাওয়া যায়, তবে তার ইনডেক্স (স্থানের অবস্থান) রিটার্ন করে।
- যদি তালিকার শেষে উপাদানটি না পাওয়া যায়, তবে জানিয়ে দেয় যে উপাদানটি তালিকায় নেই।
টাইম কমপ্লেক্সিটি:
- Best Case: O(1) (যদি প্রথমেই উপাদানটি পাওয়া যায়)
- Worst Case: O(n) (যদি উপাদানটি না থাকে বা তালিকার একেবারে শেষে থাকে)
উদাহরণ:
def linear_search(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i # উপাদানের ইনডেক্স ফেরত দিচ্ছে
return -1 # উপাদানটি নেই বোঝাচ্ছে
বাইনারি সার্চ (Binary Search)
বাইনারি সার্চ একটি কার্যকর সার্চ অ্যালগরিদম, যা শুধু বিন্যস্ত তালিকার উপর কাজ করে। এই অ্যালগরিদমটি ক্রমান্বয়ে তালিকাকে দুইভাগে ভাগ করে এবং উপাদানটি কোন ভাগে থাকতে পারে তা নির্ণয় করে খোঁজ করে।
অ্যালগরিদমের প্রক্রিয়া:
- তালিকাটি মধ্য বিন্দুতে ভাগ করা হয়।
- যদি মধ্য বিন্দুর উপাদানটি খুঁজতে চাওয়া উপাদানের চেয়ে বড় হয়, তাহলে বাম দিকের অর্ধাংশে অনুসন্ধান করে।
- যদি ছোট হয়, তাহলে ডান দিকের অর্ধাংশে অনুসন্ধান করে।
- এভাবে ক্রমান্বয়ে অংশ ভাগ করে চলতে থাকে যতক্ষণ না উপাদানটি পাওয়া যায় বা নিশ্চিত হওয়া যায় যে উপাদানটি নেই।
টাইম কমপ্লেক্সিটি:
- Best Case: O(1) (যদি প্রথমেই মধ্য বিন্দুতে উপাদানটি পাওয়া যায়)
- Worst Case: O(log n) (প্রতি পদক্ষেপে ইনপুট সাইজ অর্ধেক হচ্ছে)
উদাহরণ:
def binary_search(arr, x):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == x:
return mid # উপাদানের ইনডেক্স ফেরত দিচ্ছে
elif arr[mid] < x:
left = mid + 1
else:
right = mid - 1
return -1 # উপাদানটি নেই বোঝাচ্ছে
পার্থক্য
| বৈশিষ্ট্য | লিনিয়ার সার্চ | বাইনারি সার্চ |
|---|---|---|
| ডেটা বিন্যাস | অবিন্যস্ত বা বিন্যস্ত উভয় | কেবলমাত্র বিন্যস্ত |
| টাইম কমপ্লেক্সিটি | O(n) | O(log n) |
| কার্যপ্রণালী | প্রতিটি উপাদান চেক করা | ক্রমান্বয়ে অর্ধেক করে খোঁজা |
| এফিশিয়েন্সি | বড় ডেটাসেটে ধীর | বড় ডেটাসেটে দ্রুত |
বড় ডেটাসেটের ক্ষেত্রে, যদি তালিকা বিন্যস্ত থাকে, তবে বাইনারি সার্চ লিনিয়ার সার্চের চেয়ে অনেক দ্রুত।
Content added By
