17/11/2025
বাইনারি সার্চ কীভাবে কাজ করে? কেনই বা বাইনারি সার্চ ব্যবহার করা হয়?
ডেটা স্ট্রাকচার এন্ড অ্যালগরিদম ক্লাসের একটা সিম্পল ইয়েট অ্যামেইজিং এলগোরিদম হচ্ছে বাইনারি স্যার্চ। সহজ ভাষায় বাইনারি সার্চ কীভাবে কাজ করে আজকে সেটা নিয়ে লিখছি। আমার এই লিখাটি ভালো লাগলে জানাবেন। তাহলে পরে এমন আরো লিখার চেষ্টা করবো । আপনার মতামত স্বাগতম। ধন্যবাদ।
ধরুন আপনাকে আমি একটা সর্টেড লিস্ট বা অ্যারে দিলাম [3, 8, 15, 22, 28, 31, 49] মনে লিষ্টের সংখ্যাগুলো ছোট থেকে বড় বা বড় থেকে ছোট ক্রমে সাজানো আছে এবং বললাম এই লিস্টে 28 সংখ্যাটি আছে কিনা খুঁজে বের করতে, বা থাকলে কত তম পজিশন বা ইনডেক্সে আছে সেটা বের করতে। এখন স্বাভাবিক ভাবে আমাদের মাথায় যেই সল্যুশন আসবে সেট হচ্ছে লিস্টের প্রথম সংখ্যা থেকে শুরু করে শেষ পর্যন্ত চেক করা এবং দেখা যে এর কোনোটা আমাদের টার্গেট 28 কিনা। এই সল্যুশন অবশ্যই কার্যকর কিন্তু অনেক স্লো কাজ করবে যখন আমাদের লিস্ট অনেক বড় হবে। আমাদের লিস্টে যদি ১০০০টি সংখ্যা থাকে তাহলে এই সল্যুশনকে ১০০০ বার চেক করতে হতে পারে যদি আমাদের টার্গেট সংখ্যাটি শেষের দিকে থেকে থাকে বা একবারে না থাকে। অর্থাৎ লিস্টের সাইজ যদি n হয় তাহলে worst case scenario তে আমাদের সল্যুশনকে n সংখ্যক চেক করতে হবে যেটাকে বইয়ের ভাষায় O(n) টাইম কমপ্লেক্সিটি বলা হয়।
এখন এই একই কাজ অনেক দ্রুত করা যায় বাইনারি সার্চ অ্যালগরিদম ব্যবহার করে। যেহেতু বলা আছে আমদের লিস্টের সংখা গুলো বড় থেকে ছোট বা ছোট থেকে বড় আকারে সাজানো, তাই আমরা ইন্ডিভিডুয়ালি প্রত্যেকটা এলিমেন্ট চেক না করেই আনসার পেতে পারি। টেকনিকটা হচ্ছে যে, আমরা আমাদের লিস্টের প্রথম এবং শেষ এলিমেন্ট এর ইনডেক্সকে start এবং end হিসেবে বিবেচনা করে এদের গড় middle = (start + end) // 2 ক্যালকুলেট করতে পারি। এর পর middle এলিমেন্ট এর ভ্যালু আমাদের টার্গেট এর থেকে ছোট নাকি বড় সেটা চেক করবো। আমাদের middle এলিমেন্ট যদি টার্গেট এলিমেন্ট এর সমান হয় তাহলে তো হলই আমরা আমাদের টার্গেট খুঁজে পেয়ে গেছি। কিন্তু যদি middle > target হয় তাহলে আমাদের আমাদের টার্গেট সংখ্যাটি middle এর বাম পাশে আছে। তাই আমরা middle এর ডান পাশের সংখ্যাগুলো ইগনোর করতে পারি যেহেতু সেগুলো সবই আমাদের target সংখ্যার চেয়ে বড় হবে ।অপরভাবে যদি middle < target হয় তাহলে আমাদের target এলিমেন্ট middle এর ডান পাশে থাকবে।
উদাহরণ হিসেবে আমাদের লিস্ট nums = [3, 8, 15, 22, 28, 31, 49] এবং target = 28 হলে এখানে start = 0, end = 7, middle = (0 + 7) // 2 = 3, nums[middle] = nums[3] = 22। এখন 22 (middle) < 28 (target), তাই আমরা এখন start এর ভ্যালুকে আপডেট করতে পারি start = middle + 1 বা start = 3 + 1 = 4 নিতে পারি, আর end = 7 ই থাকছে ।এর মানে হচ্ছে আমাদের target সংখ্যা 28 লিস্টের 4th এবং 7th ইনডেক্সের মধ্যে থাকবে যদি এটি লিস্টে থেকে থাকে।
একইভাবে লুপের দ্বিতীয় ইটারেশনে start = ৪, end = ৭, middle = (4 + 7) // 2 = 5, nums[5] = 31, এবার 31 (middle) > 28 (target). আমরা তাই এবার end এর ভ্যালু আপডেট করবো middle এর ভ্যালু অনুযায়ী, end = middle - 1, বা end = 5 - 1 = 4।
এখন তৃতীয় ইটারেশনে start = 4, end = 4, middle = (4+4) // 2 = 4, nums[4] = 28 (target), তার মানে আমাদের টার্গেট সংখ্যাটি লিস্টে 4th ইনডেক্স এ আছে। আর যদি start এবং end এর ভ্যালু সমান হয়ে যায় (start == end) বা start এর ভ্যালু end এর থেকে বড় হয়ে যায় (start > end) কিন্তু এর মধ্যে আমাদের target সংখ্যা খুঁজে না পাই তার মানে আমাদের টার্গেট সংখ্যাটি লিস্টে নেই। পাইথন কোড আকারে বাইনারি সার্চ অনেকটা এমন।
def binary_search(nums, target)
start = 0 # First index
end = len(nums) - 1 # Last index
while start < end:
middle = (start + end) // 2
if nums[middle] < target:
start = middle + 1
elif nums[middle] > target:
end = middle - 1
else: # nums[middl] == target
return middle
return -1 # target not found
এখন কথা হচ্ছে এত ঝামেলা করার বেনিফিট কি ? বাইনারি সার্চে আমাদের লুপ প্রত্যেক বার লিস্টকে (সার্চ স্পেসকে) অর্ধেক করছে। অর্থাৎ আমরা প্রত্যেকবার আমাদের লিস্টকে মাঝামাঝি ভাগ করে অরপ্রয়োজনীও ভাগ কে ইগনোর করছি (ওই ভাগে আমাদের খুঁজার প্রয়োজন নেই ) এতে করে প্রত্যেক ইটারেশন পর আমাদের সার্চ স্পেস অনেক ছোট হতে থাকে। যদি আমাদের লিস্টে ১০০০ টি সংখ্যা থাকে প্রথম ইটারেশন পর ৫০০, এর পর ২৫০, এর পর ১২৫ এভাবে ছোট হতে থাকবে । অর্থাৎ আমাদের লিস্টের সাইজ যদি n হয় তাহলে আমরা সর্বোচ্চ log(n) টা চেকের মধ্যেই আনসার পেয়ে যাব যেটা লিনিয়ার সার্চের থেকে অনেক সময় সাশ্রয়ী। লিস্টের সাইজ n = ১ বিলিয়ন হলে আমাদের লিনিয়ার সার্চে যেখানে ১ বিলিয়ন চেক করতে হতে পারে সেট বাইনারি সার্চ ব্যবহার করে সর্বোচ্চ ৩০টা সার্চ করেই খুঁজতে পারবো! ১ বিলিয়ন চেক vs মাত্র ৩০টা চেক! এজন্য প্রোগ্রামাররা অনেক সময়েই O(n) (liniar time complexity) অ্যালগরিদম এর থেকে O(log(n)) (logarithmic time complexity) এর অ্যালগরিদম বা সলিউশন বেশি প্রেফার করে কারণ এটি অনেক সময় সাশ্রয়ী যখন ইনপুট সাইজ অনেক বড় হয়। বাইনারি সার্চ প্রাকটিস করতে আগ্রহী যারা তাদের জন্য আমি কমেন্টে একটা LeetCode প্লে-লিস্ট অ্যাড করে দিচ্ছি। Happy Coding!
