পাইথনে বাইনারি সার্চ (Binary Search) ব্যাখ্যা

বাইনারি সার্চ (Binary search) হলো একটি সার্চিং অ্যালগরিদম যা একটি সর্ট করা অ্যারে (sorted array) থেকে একটি এলিমেন্ট খুঁজে বের করতে ব্যবহৃত হয়। এটি আনসর্টেড (unsorted) অ্যারে থেকে সার্চ করতে ব্যবহার করা যায় না। বাইনারি সার্চ একটি দক্ষ অ্যালগরিদম এবং লিনিয়ার সার্চ (linear search) চেয়ে টাইম কমপ্লেক্সিটি দৃষ্টিতে ভালো।

লিনিয়ার সার্চের টাইম কমপ্লেক্সিটি O(n)। অন্যদিকে বাইনারি সার্চের টাইম কমপ্লেক্সিটি O(log n)। তাই বাইনারি সার্চ একটি দক্ষ এবং দ্রুত সার্চিং অ্যালগরিদম কিন্তু শুধু সর্ট করা অ্যারে থেকে সার্চ করতে ব্যবহার করা যায়।

বাইনারি সার্চ কীভাবে কাজ করে?

বাইনারি সার্চের মূল আইডিয়া হলো রিকোয়ার্ড এলিমেন্টটি অ্যারে সব এলিমেন্টের সাথে তুলনা না করে, আমরা রিকোয়ার্ড এলিমেন্টটি অ্যারের মাঝপথের (middle) এলিমেন্টের সাথে তুলনা করব। যদি এটি সেই এলিমেন্ট হয় जिसे আমরা খুঁজছি, তবে সার্চ সফলভাবে শেষ। অন্যথায়, যদি খুঁজছি এলিমেন্টটি মাঝপথের এলিমেন্টের চেয়ে ছোট হয়, তবে নিশ্চিতভাবে এলিমেন্টটি অ্যারের প্রথম বা বাম পাশে থাকবে, কারণ অ্যারেটি সর্ট করা। একইভাবে, যদি খুঁজছি এলিমেন্টটি মাঝপথের এলিমেন্টের চেয়ে বড় হয়, তবে নিশ্চিতভাবে এলিমেন্টটি অ্যারের দ্বিতীয় আধা বা ডান পাশে থাকবে।

এভাবে বাইনারি সার্চ ক্রমাগত অ্যারেকে আধা করে ফেলে। উপরের প্রক্রিয়া নির্বাচিত অ্যারের আধা भागে রিকার্সিভলি প্রয়োগ করা হয় যতক্ষণ না আমরা খুঁজছি এলিমেন্টটি পাওয়া যায়।

আমরা বাম ইনডেক্স ০ এবং ডান ইনডেক্স অ্যারের লাস্ট ইনডেক্স দিয়ে সার্চ শুরু করব। মাঝপথের এলিমেন্টের ইনডেক্স (mid) ক্যালকুলেট করা হয় যা বাম এবং ডান ইনডেক্সের যোগফল ২ দিয়ে ভাগ। যদি রিকোয়ার্ড এলিমেন্ট মাঝপথের এলিমেন্টের চেয়ে ছোট হয়, তবে ডান ইনডেক্স mid-1 এ পরিবর্তন করা হয়, অর্থাৎ আমরা এখন শুধু অ্যারের প্রথম আধা অংশে নজর দেব। একইভাবে, যদি রিকোয়ার্ড এলিমেন্ট মাঝপথের এলিমেন্টের চেয়ে বড় হয়, তবে বাম ইনডেক্স mid+1 এ পরিবর্তন করা হয়, অর্থাৎ আমরা এখন শুধু অ্যারের দ্বিতীয় আধা অংশে নজর দেব। আমরা নির্বাচিত অ্যারের আধা অংশের জন্য উপরের প্রক্রিয়া রিপিট করব।

কীভাবে বুঝব এলিমেন্ট অ্যারেতে নেই?

আমাদের কিছু কন্ডিশন থাকতে হবে যা সার্চ বন্ধ করতে বলে এবং ইঙ্গিত দেবে এলিমেন্ট অ্যারেতে নেই। আমরা এলিমেন্টটি অ্যারেতে ইটারেটিভলি (iteratively) সার্চ করব যতক্ষণ না বাম ইনডেক্স ডান ইনডেক্সের চেয়ে ছোট বা সমান হয়। একবার এই কন্ডিশন মিথ্যা হয়ে যায় এবং এখনও আমরা এলিমেন্টটি খুঁজে পাইনি, তবে এর মানে এলিমেন্টটি অ্যারেতে নেই।

উদাহরণ

নিচের সর্ট করা অ্যারেটি নেওয়া যাক এবং আমাদের এলিমেন্ট ৬ খুঁজে বের করতে হবে।

L=0 H=8 Mid=4

6 < 10, তাই প্রথম আধা অংশ নেওয়া হবে।

H = Mid-1

L=0 H=3 Mid=1

6 > 5, তাই দ্বিতীয় আধা অংশ নেওয়া হবে।

L = Mid+1

L=2 H=3 Mid=2

6 == 6, এলিমেন্ট পাওয়া গেলো।

অতএব এলিমেন্ট ৬ ইনডেক্স ২-তে পাওয়া গেলো।

ইমপ্লিমেন্টেশন

একটি সর্ট করা অ্যারে দেওয়া থাকলে, একটি রিকোয়ার্ড এলিমেন্ট সার্চ করুন এবং এলিমেন্টটি অ্যারেতে থাকলে এর ইনডেক্স প্রিন্ট করুন। যদি এলিমেন্টটি না থাকে, তবে -1 প্রিন্ট করুন।

বাইনারি সার্চ ইমপ্লিমেন্টেশনের কোড নিচে দেওয়া হলো:

উদাহরণ

def binary_search(arr, x):
    l = 0
    r = len(arr) - 1
    while l <= r:
        mid = (l + r) // 2
        if arr[mid] == x:
            return mid
        elif x < arr[mid]:
            r = mid - 1
        elif x > arr[mid]:
            l = mid + 1
    return -1

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
a = 7
print(binary_search(array, a))
b = 15
print(binary_search(array, b))

আউটপুট

6
-1

এলিমেন্ট ৭ ইনডেক্স ৬-তে আছে।

এলিমেন্ট ১৫ অ্যারেতে নেই, তাই -1 প্রিন্ট হয়েছে।