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

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

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

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

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

 কার্যপদ্ধতি 

 আসন্ন মিল 

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

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

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

 হ্যাশিং 

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

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

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

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

 রকমফের 

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

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

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

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

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

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

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

 ইতিহাস 

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

 লাইব্রেরি সহায়তা 

 আরও দেখুন 
 দ্বিখন্ডন পদ্ধতি - একই ধারণা যা বাস্তব সংখ্যার সমীকরণ সমাধান এ প্রয়োগ করা হয়।
 বর্ধক বাইনারি অনুসন্ধান - এক রকম বাইনারি অনুসন্ধান যাতে মধ্যবিন্দু নির্নয় আরও সহজতর।

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

 বহিঃসংযোগ 
 NIST Dictionary of Algorithms and Data Structures: binary search
বাইনারি সার্চ (Binary search) ও তার অ্যালগরিদম

বিষয়শ্রেণী:কম্পিউটার বিজ্ঞান
বিষয়শ্রেণী:অনুসন্ধান অ্যালগোরিদম
বিষয়শ্রেণী:২
বিষয়শ্রেণী:২ (সংখ্যা)