বাইনারি সার্চ (Binary search) ও তার অ্যালগরিদম
Binary search Bangla tutorial/ Binary search implementation/ Binary search using C++
বাইনারি সার্চ কি? বাইনারি সার্চ অ্যালগরিদম (Binary search algorithm) হলো কম্পিউটার সাইন্সের (Computer Science) কিছু ফান্ডামেন্টাল অ্যালগরিদম গুলোর মধ্যে অন্যতম। এই অ্যালগরিদমটি দিয়ে একটি সর্টেড অ্যারেতে (ছোট থেকে বড় অথবা বড় থেকে ছোট) একটি ইলিমেন্ট আছে কিনা তা সময় এ খুঁজে বের করা যায়। যেখানে লিনিয়ার সার্চ অ্যালগরিদম ইলিমেন্টটি খুজতে সময় নেয়।
এর পরের লিখা টারনারি সার্চ নিয়ে যা এখানে গিয়ে পড়তে পারেন।
বাইনারি সার্চ বনাম লিনিয়ার সার্চ
লিনিয়ার সার্চে (Linear search) অ্যারে থেকে একটা ইলিমেন্ট খুঁজে বের করা হয় পর্যায়ক্রমিক ভাবে অ্যারেতে খুঁজে। আমরা যতক্ষণ না পর্যন্ত ইলিমেন্টটি খুজে পাবো অথবা অ্যারের শেষে না যাবো, ততক্ষণ পর্যন্ত আমাদেরকে খুঁজতে হবে।
অপরদিকে বাইনারি সার্চে আমরা একটি সর্টেড অ্যারে (Sorted array) ব্যবহার করি যেখানে আমরা একটি সার্চ রেঞ্জের মাঝখানের ইলিমেন্টকে সবসময় বিবেচনা করি। যদি মাঝখানের ইলিমেন্টটা আমাদের টার্গেট না হয় তবে হয় ডানে অথবা বামে যেতে হয়। সম্পূর্ণ অ্যারে ঘুরে দেখার কোন প্রয়োজন পরে না।
বাইনারি সার্চ বুঝার জন্য আমরা একটি বাস্তব জীবনের উদাহরণ দেয়ার চেস্টা করছি। ধরা যাক আমাদেরকে একটি বই দেয়া আছে। বইয়ের পৃষ্ঠা আছে মোট ২০২০ টি। আমাদেরকে ১৭০৫ নং পৃষ্ঠাটি খুঁজে বের করতে হবে। তাহলে আমরা কিভাবে করতাম? চলুন ভাবি,
বাইনারি সার্চের (Binary search) মতো করে বইয়ের পৃষ্ঠা খুঁজে বের করা
- প্রথমেই আমরা বইয়ের মাঝামাঝি একটি পৃষ্ঠাকে সূত্র মেনে বের করে ফেলতাম। এই সূত্র মেনে আমরা ১০১০ নং পৃষ্ঠা খুললাম।
- তারপর আমরা দেখতাম যেই পৃষ্ঠা খুলেছি (১০১০ নং পৃষ্ঠা) ওই পৃষ্ঠাটি টার্গেট পৃষ্ঠা ১৭০৫ থেকে সমান না বড় না ছোট।
- এক্ষেত্রে ১০১০ আমাদের টার্গেট থেকে ছোট। সুতরাং আমরা নিশ্চিত যে আমাদের টার্গেট বইয়ের ১-১০১০ পৃষ্ঠার মধ্যে নাই। যেহেতু বই এর প্রতিটি পৃষ্ঠা ছোট থেকে বড় আকারে সাজানো আছে। তাই আমরা প্রথম অর্ধেক কে বিবেচনার বাইরে রেখে দিবো এবং বইয়ের ডানে যাবো।
- আমরা ডানের টুকু মানে ১০১১ থেকে ২০২০ পর্যন্ত নিয়ে এর মাঝামাঝি খুলে ফেলবো। ধরা যাক এবার আমরা ১৫১৫ নাম্বার পৃষ্ঠা খুলেছি। আমরা আবার মিলিয়ে দেখবো ১৫১৫ কি ১৭০৫ এর থেকে সমান, নাকি ছোট অথবা বড়। এখানে দেখতে পাচ্ছি ১৫১৫ এখনও আমাদের টার্গেট (১৭০৫) থেকে ছোট। তাই ৩ নং এর মতো করেই আমরা ১০১১ থেকে ১৫১৫ নং পৃষ্ঠা বাদ দিবো। এবং ডানে যাবো।
- এবার আমরা ১৫১৬ থেকে ২০২০ পর্যন্ত বিবেচনা করছি। একই ভাবে আমরা মাঝ বরাবর খুলে ফেলেছি এবং ১৭৬৮ নাম্বার পৃষ্ঠা বের করলাম। এখানে ১৭৬৮ আমাদের টার্গেট ১৭০৫ থেকে বেশি। তাই আমরা ১৫১৬ থেকে ১৭৬৮ বিবেচনা করবো অর্থাৎ বামে যাবো। তাই ১৭৬৮ থেকে ২০২০ পৃষ্ঠা বাদ যাবে।
- এখন আমরা ১৫১৬ – ১৭৬৭ এর মাঝ বরাবর খুলবো যেই পৃষ্ঠাটি হলো ১৬৪১। যেহেতু এই পৃষ্ঠা আমাদের টার্গেট থেকে কম তাই আমরা ডান অংশে (১৬৪৩-১৭৬৭) পৃষ্ঠা বিবেবচনা করে আবার তাদের মাঝের পেজ ১৭০৫ খুলবো।
- এখানে ১৭০৫ নং পেজটিই আমাদের টার্গেট পেজ।
উপরে আমরা বই থেকে পৃষ্ঠা খুঁজার যেই অ্যালগরিদমটি দেখলাম এই অ্যালগরিদমটিই বাইনারি সার্চ অ্যালগরিদম। আমরা চিন্তা করি, যদি আমরা এভাবে না দেখে একের পর এক পৃষ্ঠা খুলে দেখতাম (লিনিয়ার সার্চের মতো করে) তবে কেমন হতো? কি পরিমাণ সময় লাগতো? অনেক সময় লাগত আসলে।
প্রোগ্রামিং এ বাইনারি সার্চের ইমপ্লিমেন্ট করা খুবই সহজ। আমরা উপরে যেভাবে বললাম সেভাবেই কাজ করবো। আমরা একটি অ্যারে নিবো এবং অ্যারেটিকে আগেই সর্ট করে নিবো। তারপর আমরা নিচের মতো প্রসেস করবো।
- শুরুতে আমাদের যেখানে n হলো অ্যারে এর সাইজ এবং l ও r হলো অ্যারের বাম এবং ডান ইনডেক্স (আমরা 0 থেকে n-1 নিলাম কারণ অ্যারে তে শুন্য ভিত্তিক ইনডেক্স হয়)। আমরা প্রদত্ত অ্যারেটাকে সর্ট করে নিবো ছোট থেকে বড় (Ascending order) এ।
- যদি হয় তবে, l এবং r এর মাঝখানের ইনডেক্সে বা এ যে ইলেমেন্ট আছে আমরা সেখান থেকে শুরু করবো।
- যদি মাঝখানের উপদান আমাদের টার্গেট এর সমান হয় তবে আমরা আমাদের টার্গেটকে অ্যারেতে পেয়ে গেছি।
- যদি না পাই তবে আমরা মাঝের ইলিমেন্টের সাথে টার্গেট ভ্যালুকে তুলনা করে দেখি।
- যদি টার্গেট ভ্যালু আমাদের মাঝের ভ্যালু থেকে ছোট হয় তবে আমরা r=mid-1 সেট করবো।
- অন্যথায় যদি টার্গেট ভ্যালু মাঝের থেকে বড় হয় তবে আমরা l=mid+1 সেট করবো।
- আমরা পুনরায় দুই নং ধাপ থেকে শুরু করবো।
- অথবা যদি হয়ে যায়, তার মানে হলো আমরা ইলিমেন্টটি অ্যারেতে খুঁজে পাই নি।
বাইনারি সার্চ ইমপ্লিমেন্টেশন (Implementing binary search)
বাইনারি সার্চ অ্যালগরিদম বেশ কিছু ভাবে ইমপ্লিমেন্ট করা যায়। আমরা ৩ টি উপায় দেখবো। প্রথমটি দেখবো লুপের মাধ্যমে। দ্বিতীয়টি রিকার্শনের মাধ্যমে এবং তৃতীয় টি অ্যারেতে জাম্প (Jump) করার মাধ্যমে।
লুপের মাধ্যমে বাইনারি সার্চ ইমপ্লিমেন্ট করা
লুপের মাধ্যমে বাইনারি সার্চ ইমপ্লেমেন্ট করার জন্য আমরা উপরের অ্যালগরিদমে যেভাবে বলেছই হুবুহু সেভাবেই করবো। নিচের কোডটি দেখি।
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <bits/stdc++.h> using namespace std; int main(){ int n=9; int arr[n] ={5,3,4,7,8,2,1,8,9}; sort(arr,arr+n); int l=0,r=n-1; int target=7; while(l<=r){ int mid=(l+r)/2; if(arr[mid]==target){ cout<<target<<" found\n"; return 0; }else if(target<arr[mid]){ r=mid-1; //go left }else{ l=mid+1; //go right } } cout<<target<<" not found\n"; return 0; } |
আশা করি কোডটি সহজেই বুঝা গিয়েছে। এখানে ১২ নং লাইনে আমরা আমাদের l থেকে r রেঞ্জের মাঝের ইনডেক্স বের করছি, তারপরে অ্যালগরিদম মোতাবেক কাজ করে গিয়েছি। আমরা আরও বুঝার জন্য নিচের ডায়াগ্রাম টির ধাপগুলো লক্ষ করে দেখি। এখানে প্রতিটা ধাপ ভিজুয়ালাইজ করা হয়েছে।
রিকার্শনের মাধ্যমে বাইনারি সার্চ ইমপ্লিমেন্ট করা
রিকার্শন এর মাধ্যমে বাইনারি সার্চ করা আরও সহজ কাজ। নিচে রিকার্শনের মাধ্যমে বাইনারি সার্চ ইমপ্লিমেন্ট করার কোডটি দেয়া হলো।
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <bits/stdc++.h> using namespace std; int arr[] ={5,3,4,7,8,2,1,8,9}; int search(int l,int r,int target){ if(l>r) return -1; int mid=(l+r)/2; if(arr[mid]==target){ return mid; }else if(target<arr[mid]){ //Go left return search(l,mid-1,target); }else{ //Go right return search(mid+1,r,target); } return -1; } int main(){ int n=9; sort(arr,arr+n); int l=0,r=n-1; int target=7; if(search(l,r,target)>-1){ cout<<"Target found\n"; }else{ cout<<"Target not found\n"; } return 0; } |
জাম্প (Jump) করার মাধ্যমে বাইনারি সার্চ
এটা বাইনারি সার্চ ইমপ্লিমেন্ট করার আরেকটি উপায় যেখানে আমরা অ্যারের বাম থেকে ডানে যাবো জাম্প করে করে। আমরা প্রথম জাম্প করবো , দ্বিতীয় জাম্প করবো এভাবে আমরা জাম্প সাইজ অর্ধেক করে কমাতে থাকবো। যতক্ষণ না পর্যন্ত জাম্প সাইজ ১ না হয় ততক্ষণ। আমরা একটি জাম্প সাইজ নিয়ে ততক্ষণ লাফাতে থাকবো যতক্ষণ না পর্যন্ত আমাদের ইনডেক্স অ্যারের বাইরে চলে যায় অথবা আমরা এমন একটি অ্যারের ইনডেক্সে পৌছাই যেখানে ওই ইনডেক্সের ইলেমেন্টের মান আমাদের টার্গেট থেকে বড়। আমরা নিচর কোডটি লক্ষ করি।
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <bits/stdc++.h> using namespace std; int main(){ int n=9; int arr[n] ={5,3,4,7,8,2,1,8,9}; sort(arr,arr+n); int target=7; int k = 0; for (int b = n/2; b >= 1; b /= 2) { while (k+b < n && arr[k+b] <= target) k += b; } if (arr[k] == target) { cout<<target<<" found at index "<<k<<endl; }else{ cout<<target<<" not found\n"; } return 0; } |
এখানে আমরা প্রথম for লুপে ইনিশিয়াল জাম্প লেন্থ n/2 করে নিয়েছি। তারপর যতক্ষণ না পর্যন্ত জাম্প লেন্থ ১ না হয় ততক্ষণ পর্যন্ত আমরা লুপকে ঘুরিয়েছি। মাঝখানের while লুপের মাধ্যমে আমরা জাম্প করে করে এগিয়েছি। এগোনোর আগে আমরা চেক করে নিয়েছি স্টেপটা আমাদের রেঞ্জের মধ্যেই আছে কি না। আমরা কোডটি বুঝার জন্য নিচের গ্রাফটির সহায়তা নিবো। গ্রাফটি মনোযোগ দিয়ে দেখেন।
এখানে k এর সাথে যেসব সংখ্য যোগ করেছি তা হলো আমাদের ঐ মূহুর্তের জাম্প সাইজ৷ শুরুতে n=8 এবং জাম্প সাইজ ৪।
বাইনারি সার্চ (Binary search) অ্যালগরিদম এনালাইসিস
বাইনারি সার্চ প্রতিবার আমাদের সার্চ স্পেসকে (যে রেন্জে আমরা প্রতিবার সার্চ করি, l থেকে r পর্যন্ত) দুইভাগে ভাগ করে এবং যেকোনো একটি ভাগ সিলেক্ট করে কাজ করে। তাই আমাদের এই অ্যালগরিদমের টাইম কমপ্লেক্সিটি । আমাদের ৩ নং পদ্ধতি এর জন্যও কমপ্লেক্সিটি একই। কারণ আমাদের প্রথন for লুপে আমরা জাম্প সাইজকে সবসময় ২ দ্বারা ভাগ করতে থেকেছি। এখানে লক্ষণীয় যে দ্বিতীয় while লুপটি ২ বারে বেশি ঘুরবে না কখনো।
বাইনারি সার্চ অনেক ফাস্ট একটি অ্যালগরিদম। কেমন ফাস্ট তা বুঝতে চাইলে এই মিলিওন শব্দের ডিকশনারিতে একটি শব্দ খুঁজে বের করার চেষ্টা করে দেখতে পারেন।
অ্যারের বাইরে বাইনারি সার্চের ব্যবহার
ধরা যাক আমরা একটি সমস্যা সমাধান করছি যার একটি ফাংশন আছে, valid(x) যা x এর মানের জন্য
true রিটার্ন করবে যদি x একটি সঠিক সমাধান হয়। অন্যথায় false রিটার্ন করবে। সমস্যাটি নিম্নরূপে বর্ননা করা আছে,
valid(x), false হবে যখন হবে এবং ture হবে যখন হবে। আমরা বাইনারি সার্চ ব্যাবহার করতে পারি খুব দ্রুতভাবে k এর মান বের করতে।
আইডিয়াটি হলো আমরা দেখবো x এর সবথেকে বড় কোন মানের জন্য vailid(x), false রিটার্ন করে। কারণ তার পরের সংখ্যা k=x+1 হলো সবথেকে ছোট সংখ্যা যার জন্য আমাদের valid(x) ফাংশন true রিটার্ন করবে। এধরনের সার্চ অ্যালগরিদমকে নিচের মতো করে ইমপ্লিমেন্ট করা যাবে।
|
1 2 3 4 5 |
int x = -1; for (int b = z; b >= 1; b /= 2) { while (!valid(x+b)) x += b; } int k = x+1; |
বাইনারি সার্চের (Binary search) লিমিটেশন
বাইনারি সার্চের সবথেকে বড় লিমিটেশন হলো আমাদের একটি সর্টেড অ্যারে লাগবে সার্চ করতে। যদি আমাদের অ্যারে সর্ট করা না থাকে তাহলে আমরা সঠিক আউটপুট পাবো না।
প্রাকটিস প্রবলেমঃ https://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1552
আরও পরুনঃ সফটওয়্যার ডেভেলপমেন্ট বনাম কম্পিটিটিভ প্রোগ্রামিং, Big O notation
