Uncategorized

বাইনারি সার্চ অ্যালগরিদম – Binary Search Algorithm

binary search.jpg

#বাইনারি সার্চ অ্যালগরিদম – Binary Search Algorithm ইমপ্লিমেন্টেশন ইন পাইথন ঃ

লিনিয়ার সার্চ অ্যালগরিদমে আমারা দেখেছি কিভাবে  একটা লিস্ট থেকে   একটা একটা   করে  ইলিমেন্ট গুলোকে সিকুয়েন্সিয়েলি চেক করে কাঙ্ক্ষিত আইটেমকে খুঁজে বের করা যায়। কিন্তু এই পদ্ধতিতে আইটেমকে খুঁজে বের করা অনেক কমপ্লেক্স হয়ে যায়। ৫/১০/২০ টা লিস্টের আইটেম হয়ত  খুব সহজে খুঁজে বের করা যাবে কিন্তু আমাকে যদি ১০০০টা আইটেম দিয়ে এখান থেকে যেকোনো একটা আইটেম খুঁজে বের করতে বলে তাহলে আমি যদি  লিনিয়ার সার্চ অ্যালগরিদমে সার্চ করি তাহলে আমাকে ১০০০ বার চেক করতে হবে যা আমার পক্ষে প্রায় অসম্ভব। এতে আমার প্রোগ্রাম কমপ্লিক্সিটি অনেক বেড়ে যাবে । আর  এই  কমপ্লিক্সিটি কমানোর জন্যই আমাদের  বাইনারি সার্চ অ্যালগরিদম পদ্ধতি অনুসরণ করা ।

বাইনারি সার্চ অ্যালগরিদম কি? 

বাইনারি সার্চ অ্যালগরিদম হচ্ছে একটি  দ্রুত সার্চ  অ্যালগরিদম। এই  সার্চ  অ্যালগরিদম ডিভাইড  এন্ড কনকয়ের প্রসেস এর ভিত্তিতে কাজ করে। এই  অ্যালগরিদম তখনি কাজ করবে যখন কোন লিস্ট/এরে সরটেড/সাজানো  আকারে থাকবে । এর  কমপ্লিক্সিটি হচ্ছে  Ο(log n) যা লিনিয়ার সার্চ অ্যালগরিদমের কমপ্লিক্সিটির  O(n) এর চেয়ে অনেক ইফিসিয়েন্ট ।

একটা লিস্টকে বাইনারি সার্চ তিনটা পার্ট এ  ভাগ করেঃ ১) Low ২)  Mid  ৩) High

binsearch

মনে করি আমাদেরকে উপরের  এই লিস্ট টা দেয়া হয়েছে এবং বলা হল এর মধ্য থেকে ১৩কে খুঁজে বের করতে। প্রথমে আমরা লিস্ট থেকে মিড বের করবো। লো আর হাই তো দেখতেই পাচ্ছি। মিড বের করার জন্যে একটা সুত্র আছে ঃ  mid = low + (high – low) / 2  তাহলে আমাদের মিড হবে ঃ মিড=০+(৭-০)/২ =৩.৫ যেহেতু  ইন্ডেক্সিং  এ  ৩.৫ বলতে কিছু নাই, তাই আমরা এখানে ৩ কেই আমাদের মিড বিবেচনা করবো ।

এখন আমরা এই মিডের আইটেমের সাথে আমাদের ১৩(খুজতে চাচ্ছি) এর তুলনা করবো। যেহেতু ১৩>৭ তাই আমরা এখন মিড এর ডান দিকের অংশে খুঁজবো। বামদিক আর খুজতে হবে না কারন আমরা এখন নিশ্চিত যে বাম দিকে আমাদের ১৩ থাকতে পারে না।

এবার আবার আমরা  মিড আইটেম(৭) কে বাদ দিবো কারন ৭<১৩। এবং ইনডেক্স ৪ থেকে ৭  এর মধ্যে আমাদের আইটেম কে খুঁজবো।  এখন আমরা চিন্তা করি যে ৪  আমাদের low আর ৭ আমাদের high তাহলে আমাদের মিড হবে ঃ মিড = ৪+(৭-৪)/২= ৫.৫ মানে ৫ নাম্বার ইনডেক্স  ই হবে  আমাদের মিড। এখন আমরা আমদের মিডের ভেলুর  সাথে আমাদের আইটেম এর তুলনা করবো। যদি সমান হয় তাহলে তার ইনডেক্স নাম্বার রিটার্ন করবো। এখানে আমাদের মিড ভেলু =আমাদের আইটেম। তাহলে আমরা এখন মিড এর ইনডেক্সকে রিটার্ন করবো। তারমানে আমরা ১৩কে খুঁজে পেয়েছি ৫ নাম্বার ইনডেক্স এ । এখন আমাদের প্রোগ্রাম এই ইনডেক্স নাম্বারকেই প্রিন্ট করে দেখাবে। তাহলেই আমাদের কাজ শেষ। বিঃদ্রঃ কেউ আবার ইনডেক্স আর আইটেম এর মধ্যে গোলমাল পাকিয়ে ফেলোনা। তাইলে ভুল হবে সিউর।

বাইনারি সার্চ আর লিনিয়ার সার্চ এর মধ্যে কম্পারিজন টা দেখতে পারো  ঃ

Binary Search and Linear Search comparison

এখন আশা করি সহজেই বুঝতে পারতেসো যে কেনো আমরা বাইনারি সার্চ অ্যালগরিদম ব্যাবহার করবো।

কোড ইমপ্লিমেন্টেশনঃ 

তুমি যদি থিউরিটা ভালভাবে বুঝতে পারো তাহলে কোড ইমপ্লিমেন্ট করাটা বেশি যামেলার মনে হবে না।সহজেই পারবা।

binary search

binary

Any Suggestion or query: https://www.facebook.com/RevelYusuf

 

 

 

 

 

 

 

 

 

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s