বাইনারি অনুসন্ধান অ্যালগরিদম

কম্পিউটার বিজ্ঞানে, বাইনারি সার অর্ধ-বিরতি অনুসন্ধান, লগারিদমিক অনুসন্ধান অথবা বাইনার‍ি কর্তন নামেও পরিচিত, একটি অনুসন্ধান অ্যালগোরিদম যা একটি সজ্জিত অ্যারে হতে কাঙ্ক্ষিত মানের অবস্থানকে খুঁজে বের করে। বাইনারি অনুসন্ধান প্রথমে অ্যারের মাঝের উপাদানের সাথে কাঙ্ক্ষিত মানটির তুলনা করে; যদি তারা অসমান হয়, তাহলে যে অর্ধে কাঙ্ক্ষিত মানটি নেই তা অপসারণ করা হয় এবং পরিশিষ্ট অংশে অনুসন্ধান চলতে থাকে যতক্ষন পর্যন্ত তা সফল না হয়। যদি অবশিষ্ট অর্ধে সন্ধান না পাওয়া যায়, তাহলে কাঙ্ক্ষিত মানটি অ্যারেতে নেই।

বাইনারি অনুসন্ধান অ্যালগরিদম এর রূপচিত্র, যেখানে ৭ হল কাঙ্ক্ষিত মান।

বাইনারি অনুসন্ধান সম্পাদনে সবচেয়ে খারাপ ক্ষেত্রে লগারিদমিক সময় লাগে, এটি O(log n) সংখ্যক তুলনা করে, যেখানে n হচ্ছে অ্যারের উপাদান সংখ্যা, O হচ্ছে বিগ ওহ নোটেশন এবং log হচ্ছে লগারিদম। বাইনারি অনুসন্ধান নির্দিষ্ট (O(১)) জায়গা নেয়, যার অর্থ হল অ্যালগোরিদমটি কর্তৃক দখলকৃত স্থান অ্যারের উপাদানসংখ্যার সমান। যদিও দ্রুত অনুসন্ধানের জন্য বিশেষভাবে পরিকল্পিত ডাটা স্ট্রাকচার - যেমন হ্যাশটেবিল - অনেক কার্যকরভাবে অনুসন্ধান করা যায়, বাইনারি সার্চ বৃহত্তর পরিসরে সমস্যার ক্ষেত্রে প্রয়োগ করা যায়।

যদিও ধারণাটি সাধারণ, সঠিকভাবে বাইনারি সার্চ প্রয়োগের সময়, এটি শেষ হবার শর্তসমূহ ও মধ্যবিন্দু হিসেবের সূক্ষতার ক্ষেত্রে মনোযোগী হতে হয়।

বাইনারি অনুসন্ধানের অনেক রকমফের রয়েছে। বিশেষত, ফ্র্যাকশনাল ক্যাসকেডিং সমান মানের একাধিক অ্যারের ক্ষেত্রে গতি ত্বরান্বিত করে, গণনীয় জ্যামিতির অনুসন্ধান সমস্যাসমূহের ধারার কার্যকর সমাধান করে এবং আরও অসংখ্য ক্ষেত্র রয়েছে। বাইনারি সার্চ ট্রি ও বি-ট্রি ডাটা স্ট্রাকচারসমুহের ভিত্তি বাইনারি সার্চ।