বাইনারি সার্চ, যাকে হাফ-ইন্টারভাল সার্চ, লগারিদমিক সার্চ বা বাইনারি চপ ও বলা হয়, একটি সার্চ অ্যালগরিদম যা একটি সর্ট করা অ্যারেতে টার্গেট ভ্যালুর অবস্থান খুঁজে বের করে। বাইনারি সার্চ টার্গেট ভ্যালুর তুলনা অ্যারেতে মাঝপথের উপাদানের সাথে করে। যদি তারা সমান না হয়, তবে যে অর্ধেকটিতে টার্গেট থাকতে পারে না সেটি বাদ দিয়ে বাকি অর্ধেকটিতে সার্চ চালিয়ে যায়, আবার মাঝপথের উপাদান নিয়ে টার্গেটের সাথে তুলনা করে, এবং টার্গেট পাওয়া পর্যন্ত এই প্রক্রিয়া दुহরায়। যদি সার্চ শেষ হয়ে যায় এমন অবস্থায় যে বাকি অর্ধেকটি খালি, তবে টার্গেট অ্যারেতে নেই। আইডিয়াটি সহজ হলেও, বাইনারি সার্চ সঠিকভাবে ইমপ্লিমেন্ট করতে এক্সিট কন্ডিশন এবং মিডপয়েন্ট ক্যালকুলেশন সম্পর্কে কিছু সূক্ষ্ম বিষয়ে মনোযোগ দরকার, বিশেষ করে যদি অ্যারেতে সকল মান পুরো সংখ্যা না হয়।
বাইনারি সার্চ সবচেয়ে জনপ্রিয় সার্চ অ্যালগরিদম। এটি দক্ষ এবং προβ্লেম সমাধানে ব্যবহৃত সবচেয়ে সাধারণ টেকনিকগুলোর একটা।
যদি বিশ্বের সব নাম ক্রম대로 লিখা থাকে এবং আপনি কোনো নির্দিষ্ট নামের অবস্থান খুঁজতে চান, তবে বাইনারি সার্চ maksimum ৩৫টি ইটারেশনে এটা করতে পারবে।
বাইনারি সার্চ শুধুমাত্র সর্ট করা উপাদান সেটে কাজ করে। একটি কালেকশনে বাইনারি সার্চ ব্যবহার করতে হলে কালেকশনটি আগে সর্ট করা থাকতে হবে।
যখন একটি সর্ট করা সেটে বাইনারি সার্চ ব্যবহার করা হয়, তখন ইটারেশনের সংখ্যা যে ভ্যালু সার্চ করা হচ্ছে তার ভিত্তিতে সবসময় কমিয়ে আনা যায়।
নিচের অ্যারেটি বিবেচনা করুন:
লিনিয়ার সার্চ ব্যবহার করলে উপাদান ৮-এর অবস্থান ৯ম ইটারেশনে নির্ধারিত হবে।
আইये দেখি কিভাবে বাইনারি সার্চ ব্যবহার করে ইটারেশনের সংখ্যা কমানো যায়। সার্চ শুরু করার আগে আমাদের রেঞ্জের শুরু এবং শেষ জানতে হবে। এদের Low এবং High বলি।
Low = 0 High = n-1
এখন, সার্চ ভ্যালু K-এর তুলনা নিম্ন ও উপরের সীমার মাঝপথে অবস্থিত উপাদানের সাথে করুন। যদি K বড় হয়, তবে নিম্ন সীমা বাড়ান, অন্যথায় উপরের সীমা কমান।
উপরের ছবি অনুযায়ী, নিম্ন সীমা ০ এবং উপরের সীমা ৯। নিম্ন ও উপরের সীমার মাঝপথ = (0+9)/2 = ৪। এখানে a[4] = ৪। মান ৪ > ২ (যেটি আপনি খুঁজছেন)। তাই ৪-এর পরে যে কোনো উপাদানে সার্চ করার দরকার নেই কারণ সেগুলো očвидно ২-এর চেয়ে বড়।
তাই আমরা সহজে অ্যারেতে উপরের সীমাকে ৪ নম্বর উপাদানের অবস্থানে নামিয়ে আনতে পারি। এখন একই অ্যারেতে নিচের মানগুলো নিয়ে একই প্রক্রিয়া दुহরাই: Low: 0, High: 3। এই প্রক্রিয়াটি রিকার্সিভলি दुহরান যতক্ষণ না Low > High হয়। যদি কোনো ইটারেশনে a[mid] = key পাওয়া যায়, তবে mid-এর মান রিটার্ন করুন। এটি অ্যারেতে key-এর অবস্থান। যদি key অ্যারেতে না থাকে, তবে -১ রিটার্ন করুন।
উদাহরণ কোড
int binarySearch(int low, int high, int key) {
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] < key) {
low = mid + 1;
} else if (a[mid] > key) {
high = mid - 1;
} else {
return mid;
}
}
return -1; // key not found
}
