বাইনারি অনুসন্ধান অ্যালগরিদম
কম্পিউটার বিজ্ঞানে, বাইনারি সার অর্ধ-বিরতি অনুসন্ধান, লগারিদমিক অনুসন্ধান অথবা বাইনারি কর্তন নামেও পরিচিত, একটি অনুসন্ধান অ্যালগোরিদম যা একটি সজ্জিত অ্যারে হতে কাঙ্ক্ষিত মানের অবস্থানকে খুঁজে বের করে। বাইনারি অনুসন্ধান প্রথমে অ্যারের মাঝের উপাদানের সাথে কাঙ্ক্ষিত মানটির তুলনা করে; যদি তারা অসমান হয়, তাহলে যে অর্ধে কাঙ্ক্ষিত মানটি নেই তা অপসারণ করা হয় এবং পরিশিষ্ট অংশে অনুসন্ধান চলতে থাকে যতক্ষন পর্যন্ত তা সফল না হয়। যদি অবশিষ্ট অর্ধে সন্ধান না পাওয়া যায়, তাহলে কাঙ্ক্ষিত মানটি অ্যারেতে নেই।
বাইনারি অনুসন্ধান সম্পাদনে সবচেয়ে খারাপ ক্ষেত্রে লগারিদমিক সময় লাগে, এটি O(log n) সংখ্যক তুলনা করে, যেখানে n হচ্ছে অ্যারের উপাদান সংখ্যা, O হচ্ছে বিগ ওহ নোটেশন এবং log হচ্ছে লগারিদম। বাইনারি অনুসন্ধান নির্দিষ্ট (O(১)) জায়গা নেয়, যার অর্থ হল অ্যালগোরিদমটি কর্তৃক দখলকৃত স্থান অ্যারের উপাদানসংখ্যার সমান। যদিও দ্রুত অনুসন্ধানের জন্য বিশেষভাবে পরিকল্পিত ডাটা স্ট্রাকচার - যেমন হ্যাশটেবিল - অনেক কার্যকরভাবে অনুসন্ধান করা যায়, বাইনারি সার্চ বৃহত্তর পরিসরে সমস্যার ক্ষেত্রে প্রয়োগ করা যায়।
যদিও ধারণাটি সাধারণ, সঠিকভাবে বাইনারি সার্চ প্রয়োগের সময়, এটি শেষ হবার শর্তসমূহ ও মধ্যবিন্দু হিসেবের সূক্ষতার ক্ষেত্রে মনোযোগী হতে হয়।
বাইনারি অনুসন্ধানের অনেক রকমফের রয়েছে। বিশেষত, ফ্র্যাকশনাল ক্যাসকেডিং সমান মানের একাধিক অ্যারের ক্ষেত্রে গতি ত্বরান্বিত করে, গণনীয় জ্যামিতির অনুসন্ধান সমস্যাসমূহের ধারার কার্যকর সমাধান করে এবং আরও অসংখ্য ক্ষেত্র রয়েছে। বাইনারি সার্চ ট্রি ও বি-ট্রি ডাটা স্ট্রাকচারসমুহের ভিত্তি বাইনারি সার্চ।
অ্যালগোরিদম সম্পাদনা
বাইনারি অনুসন্ধান সজ্জিত অ্যারের ওপর কাজ করে। বাইনারি অনুসন্ধান কাঙ্ক্ষিত মানের সাথে অ্যারের মাঝ উপাদানের তুলনার মাধ্যমে শুরু হয়। যদি কাঙ্ক্ষিত মানের সাথে মাঝ উপাদান মিলে যায় তাহলে অ্যারে হতে এর অবস্থান ফেরত আসে। যদি কাঙ্ক্ষিত মান ছোট বা বড় হয় তবে যথাক্রমে অ্যারের নিচের বা উপরের অর্ধে অনুসন্ধান চলতে থাকে এবং বিবেচনা হতে অপর অর্ধ অপসারিত হয়।
কার্যপদ্ধতি সম্পাদনা
আসন্ন মিল সম্পাদনা
কর্মক্ষমতা সম্পাদনা
টাইম কম্পেক্সিটি - O(log n)
স্পেস - O(1)
বাইনারি অনুসন্ধান বনাম অন্যান্য পদ্ধতি সম্পাদনা
হ্যাশিং সম্পাদনা
ট্রিস সম্পাদনা
রৈখিক অনুসন্ধান সম্পাদনা
সদস্য নির্ধারক অ্যালগোরিদম সম্পাদনা
অন্যান্য উপাত্ত সংগঠনসমূহ সম্পাদনা
রকমফের সম্পাদনা
অভিন্ন বাইনারি অনুসন্ধান সম্পাদনা
সূচকীয় অনুসন্ধান সম্পাদনা
প্রক্ষেপক অনুসন্ধান সম্পাদনা
ফ্র্যাকশনাল ক্যাসকেডিং সম্পাদনা
ফিবোনাচ্চি অনুসন্ধান সম্পাদনা
গোলমেলে বাইনারি অনুসন্ধান সম্পাদনা
কোয়ান্টাম বাইনারি অনুসন্ধান সম্পাদনা
ইতিহাস সম্পাদনা
বাস্তবায়ন ইস্যুসমূহ সম্পাদনা
লাইব্রেরি সহায়তা সম্পাদনা
আরও দেখুন সম্পাদনা
- দ্বিখন্ডন পদ্ধতি - একই ধারণা যা বাস্তব সংখ্যার সমীকরণ সমাধান এ প্রয়োগ করা হয়।
- বর্ধক বাইনারি অনুসন্ধান - এক রকম বাইনারি অনুসন্ধান যাতে মধ্যবিন্দু নির্নয় আরও সহজতর।