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

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

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

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

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

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

অ্যালগোরিদমসম্পাদনা

বাইনারি অনুসন্ধান সজ্জিত অ্যারের ওপর কাজ করে। বাইনারি অনুসন্ধান কাঙ্ক্ষিত মানের সাথে অ্যারের মাঝ উপাদানের তুলনার মাধ্যমে শুরু হয়। যদি কাঙ্ক্ষিত মানের সাথে মাঝ উপাদান মিলে যায় তাহলে অ্যারে হতে এর অবস্থান ফেরত আসে। যদি কাঙ্ক্ষিত মান ছোট বা বড় হয় তবে যথাক্রমে অ্যারের নিচের বা উপরের অর্ধে অনুসন্ধান চলতে থাকে এবং বিবেচনা হতে অপর অর্ধ অপসারিত হয়।

কার্যপদ্ধতিসম্পাদনা

আসন্ন মিলসম্পাদনা

কর্মক্ষমতাসম্পাদনা

টাইম কম্পেক্সিটি - O(log n)

স্পেস - O(1)

 
বাইনারি অনুসন্ধান চিত্রিতকারী একটি ট্রি। যে অ্যারেটিতে অনুসন্ধান করা হচ্ছে তা হল [২০,৩০,৪০,৫০,৮০,৯০,১০০], এবং কাঙ্ক্ষিত মান ৪০।

বাইনারি অনুসন্ধান বনাম অন্যান্য পদ্ধতিসম্পাদনা

হ্যাশিংসম্পাদনা

ট্রিসসম্পাদনা

 
বাইনারি অনুসন্ধান এর সদৃশ অ্যালগোরিদম অনুসারে বাইনারি অনুসন্ধান ট্রিতে অনুসন্ধান করা হচ্ছে।

রৈখিক অনুসন্ধানসম্পাদনা

সদস্য নির্ধারক অ্যালগোরিদমসম্পাদনা

অন্যান্য উপাত্ত সংগঠনসমূহসম্পাদনা

রকমফেরসম্পাদনা

অভিন্ন বাইনারি অনুসন্ধানসম্পাদনা

 
অভিন্ন বাইনারি অনুসন্ধান নির্দিষ্ট সীমার পরিবর্তে বর্তমান ও সম্ভাব্য পরবর্তী দুটি মধ্যমানের অন্তর জমা রাখে।

সূচকীয় অনুসন্ধানসম্পাদনা

প্রক্ষেপক অনুসন্ধানসম্পাদনা

ফ্র্যাকশনাল ক্যাসকেডিংসম্পাদনা

ফিবোনাচ্চি অনুসন্ধানসম্পাদনা

গোলমেলে বাইনারি অনুসন্ধানসম্পাদনা

কোয়ান্টাম বাইনারি অনুসন্ধানসম্পাদনা

ইতিহাসসম্পাদনা

বাস্তবায়ন ইস্যুসমূহসম্পাদনা

লাইব্রেরি সহায়তাসম্পাদনা

আরও দেখুনসম্পাদনা

তথ্যসূত্র ও পাদটীকাসম্পাদনা

বহিঃসংযোগসম্পাদনা