இருமத் தேடல் அல்கோரிதம்
{{தலைப்பை மாற்றுக}}
 [[கணினி]] [[அறிவியல்|அறிவியலில்]], '''இருமத் தேடல்''', அல்லது '''அரை-இடைவெளித் தேடல்''',&lt;ref&gt;{{cite conference|last1=Willams, Jr.|first1=Louis F.|title=A modification to the half-interval search (binary search) method|conference=Proceedings of the 14th ACM Southeast Conference|date=1975|pages=95–101|doi=10.1145/503561.503582}}&lt;/ref&gt; '''மடக்கைத் தேடல்''',{{Sfn|Knuth|1998|loc=§6.2.1 (&quot;Searching an ordered table&quot;), subsection &quot;Binary search&quot;}} அல்லது '''இருமத் தறித்தல்''',{{Sfn|Butterfield|Ngondi|2016}} என்பது ஒரு தேடல் அலகோரிதம் அல்லது தேடல் படிமுறைத் தீர்வாகும். இது குறிப்பிட்ட தேர்ந்தெடுத்த அணிக்குள் இலக்கு மதிப்பு இருப்பிட்த்தைக் கண்டுபிடித்தலாகும்.{{Sfn|Cormen|Leiserson|Rivest|Stein|2009|p=39}}&lt;ref&gt;{{MathWorld |title=Binary Search |id=BinarySearch}}&lt;/ref&gt; இருமத் தேடல் இலக்கு மதிப்பை அணியின் நடு உறுப்போடு ஒப்பிடுகிறது; அவை சமமாக அமையாவிட்டால், இலக்கு மதிப்பு அமையமுடியாத அரைப்பகுதி நீக்கப்படும்; தேடல் எஞ்சிய அரைப்ப்பகுதியில் வெற்றி கிடைக்கும் வரை தொடரும். எஞ்சிய அரைப்பகுதியில் வெற்றாகத் தேடல் முடிவுற்றால், அந்த அணிக்குள் இலக்கு மதிப்பு இல்லை என்று பொருள்.
 
 இருமத் தேடல் அரிய மடக்கை நேரத்தில்,  {{math|{{italics correction|''O''}}(log ''n'')}} இன் ஒப்பீடுகளைச் செய்து செயல்படுகிறது. இங்கு, {{mvar|n}} என்பது அணியில் அமையும் உறுப்புகளின் எண்ணிக்கை ஆகும்;  {{math|''O''}} என்பது பேரெழுத்து O சார்ந்த  குறிமானம் ஆகும் ;  {{math|log}} என்பது மடக்கையாகும். இருமத் தேடல் நிலையான ({{math|{{italics correction|''O''}}(1)}}) வெளியை எடுத்துக் கொள்கிறது; இதன் பொருள், அணியில் உள்ள உறுப்புகளின் எண்ணிக்கை மாறுபட்டாலும் அல்கோரிதத்தில் அதற்காக அமையும் வெளி ஒரே அளவாகவே அமையும் என்பதாகும்.&lt;ref name=&quot;avgperf&quot;&gt;{{cite journal|last1=Flores|first1=Ivan|last2=Madpis|first2=George|title=Average binary search length for dense ordered lists|journal=[[Communications of the ACM]]|date=1971|volume=14|issue=9|doi=10.1145/362663.362752|pages=602–603}}&lt;/ref&gt; விரைவுப் பட்டியல் போன்ற விரைவாகத் தேடும் சிறப்புத் தரவுக் கட்டமைப்புகள் இருந்தாலும், இருமத் தேடல் அகல்நெடுக்கமான பல பயன்பாட்டுச் சிக்கல்களுக்கு ஏற்றதானதாக உள்ளது.
 
 இந்த எண்ணக்கரு எளியதாகத் தோன்றினாலும், சரியாக இருமத் தேடலை நடைமுறைப்படுத்த, அவற்றின் நடுப்புள்ளியைக் கணக்கிடுவதிலும் கணிப்பு முடித்து வெளியேறும் நிலைமைகளிலும் நிலவும் சில நுட்பங்களில் கவனம் செலுத்த வேண்டிய தேவைகள் உள்ளன.
 
 இருமத் தேடலில் பல வேறுபாடுள்ள முறைகள் உள்ளன. குறிப்பாக பகுதி ஓடையாக்க முறை, ஒரே இலக்கு மதிப்புக்கு பல அணிகளில் தேடுவதால் இருமத் தேடல்களின் வேகத்தைக் கூட்டுகிறது; கணிப்பு வடிவவியலிலும் எண்ணற்ற பிற புலங்களிலும் உள்ள தேடல் சிக்கலகளுக்குத் திறமையான தீர்வுகளை காண்கிறது. படியேற்ற முறைத் தேடல் இருமத் தேடலை வரம்பற்ர பட்டியல்களுக்கு விரிவாக்குகிறது. இருமத் தேடல் தருவும் B-தருவும் சார்ந்த தரவுக் கட்டமைப்புகள் இருமத் ஹ்டேடலைச் சார்ந்தவையே.
 
 == படிமுறைத் தீர்வு (அல்கோரிதம்) ==
 
 இருமத் தேடல் வரிசையான உறுப்புகள் அமைந்த அணிகளில் வேலை செய்கிறது. இலக்கு மதிப்பை அணியின் நடு உறுப்புடன் ஒப்பிடுவதன் வாயிலாக தன் தேடலை இருமத் தேடல் தொடங்குகிறது. இலக்கு மதிப்பும் நடு உறுப்பு மதிப்பும் ஒன்றினால் அணியின் இருப்பு தீர்மானமாகித் தேடல் முடிவடைகிறது. நடுவுறுப்பின் மதிப்புக்கு இலக்கு மதிப்பு குறைவாகவோ கூடுதலாகவோ இருந்தால், தேடல் முறையே அணியின் கீழ் அல்லது மேல் அரைப்பகுதியில், மற்ற அரைப்பகுதியைத் தவிர்த்துவிட்டு,  தேடலைத் தொடர்கிறது .{{Sfn|Knuth|1998|loc=§6.2.1 (&quot;Searching an ordered table&quot;), subsection &quot;Algorithm B&quot;}}
 
 ===வழிமுறை===
 ''A''&lt;sub&gt;0&lt;/sub&gt; ≤ ''A''&lt;sub&gt;1&lt;/sub&gt; ≤ ... ≤ ''A''&lt;sub&gt;''n''−1&lt;/sub&gt; என்ற முறையில் வரிசை படுத்தப்பட்ட, ''A''&lt;sub&gt;0&lt;/sub&gt;, ''A''&lt;sub&gt;1&lt;/sub&gt;, ..., ''A''&lt;sub&gt;''n''−1&lt;/sub&gt; எனும் உறுப்பு மதிப்புகளை/பதிவுகளைக்  கொண்ட  ''n'' உறுப்புகள் அமைந்த ''A'' அணியைக் கருதுவோம். தேடும் இலக்கு மதிப்பு ''T'' எனில், பின்வரும் இயல்நிரல் ''A'' அணியில் அமைந்த ''T'' சுட்டியைக் கண்டுபிடிக்கும் இருமத் தேடலை நிகழ்த்துகிறது.{{Sfn|Knuth|1998|loc=§6.2.1 (&quot;Searching an ordered table&quot;), subsection &quot;Algorithm B&quot;}}
 
 #  ''L'' மதிப்பு  0 எனில், மேலும் ''R''  மதிப்பு ''n'' எனில், &amp;minus; 1.
 #  ''L'' மதிப்பு  &gt; ''R'' எனில், தேடல் தோல்வியில் முடிகிறது.
 # ''m'' (நடு உறுப்பின் இருப்பு) மதிப்பை (''L'' + ''R'') / 2 எனும் தரை மதிப்பாகக் ( முந்தைய மிகப் பெரிய எண்) கொள்க.
 #  ''A''&lt;sub&gt;''m''&lt;/sub&gt; &lt; ''T'' எனில்,  ''L''  மதிப்பை ''m'' + 1 ஆகக் கொண்டு  இரண்டாம் படிநிலைக்குச் செல்க.
 #  ''A''&lt;sub&gt;''m''&lt;/sub&gt; &gt; ''T'' எனில்,  ''R'' மதிப்பை ''m'' &amp;minus; 1 ஆகக் கொண்டு இரண்டாம் படிநிலைக்குச் செல்க.
 # இப்போது ''A''&lt;sub&gt;''m''&lt;/sub&gt; = ''T'' எனில், தேடல் முடிந்தது;  ''m'' மதிப்புக்கு மீள்க.
 
 இந்த திருபத் திரும்ப பலமுறை செய்யும் வழிமுறை (பன்னிச் செயல்முறை-iteration) இரு மாறிகளின் தேடல் வரம்புகளைக் கண்காணித்துக் கொள்கிறது.
 
 ==நூலக உதவி==
 பல நிரலாக்க மொழிக்கான செந்தர நூலகங்களில் இருமத் தேடல் அல்கோரித இயல்நிரல்கள் உள்ளன:
 * C நிரலாக்க மொழி, இதற்கான சார்பைத் (இயல்நிரலைத்) &lt;code&gt;bsearch()&lt;/code&gt; எனும் தனது C  செந்தர நூலகத்தில் தருகிறது. இந்நிரல் இருமத் தேடல் வழியிலேயே நடைமுறைப்படுத்தப்படுகிறது. என்றாலும் அதன் அலுவல்முறைப் பதிப்பில் இது வேண்டப்படுவதில்லை.&lt;ref&gt;{{cite web|title=bsearch – binary search a sorted table|url=http://pubs.opengroup.org/onlinepubs/9699919799/functions/bsearch.html|website=The Open Group Base Specifications|edition=7th|publisher=[[The Open Group]]|accessdate=28 March 2016|date=2013}}&lt;/ref&gt;
 * C++  மொழியின் செந்தர வார்ப்புரு நூலகமும் &lt;code&gt;இருமத் தேடல்()&lt;/code&gt; சார்ந்த &lt;code&gt;கீழ் வரம்பு()&lt;/code&gt;, &lt;code&gt;மேல் வரம்பு()&lt;/code&gt;,  &lt;code&gt;சம நெடுக்கம்()&lt;/code&gt; ஆகிய சார்புகளைத் தருகிறது.{{Sfn|Stroustrup|2013|loc=§32.6.1 (&quot;Binary Search&quot;)}}
 * கோபால்(COBOL) மொழி, கோபால் வரிசை அட்டவணைகளில் இருமத் தேடலை நிகழ்த்துவதற்கான&lt;code&gt;தேடு அனைத்தும்&lt;/code&gt; எனும் வினையைத் தருகிறது.&lt;ref&gt;{{Citation|title=COBOL ANSI-85 Programming Reference Manual|author=[[Unisys]]|date=2012|volume=1|pp=598–601}}&lt;/ref&gt;
 * ஜாவா நிரலாக்க மொழி, ஜாவா அணிகளிலும் பட்டியல்களிலும் இருமத் தேடலை நிகழ்த்தும் மிகைச்சுமையுள்ள  &lt;code&gt;இருமத் தேடல்()&lt;/code&gt; சார்ந்த நிலையியல் முறைகளின் கணத்தை {{Javadoc:SE|java/util|Arrays}},  {{Javadoc:SE|java/util|Collections}}  ஆகிய வகைகளில் தனது செந்தர &lt;code&gt;java.util&lt;/code&gt; தொகுப்பில் தருகிறது.&lt;ref&gt;{{cite web|title={{mono|java.util.Arrays}}|url=https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html|website=Java Platform Standard Edition 8 Documentation|publisher=[[Oracle Corporation]]|accessdate=1 May 2016}}&lt;/ref&gt;&lt;ref&gt;{{cite web|title={{mono|java.util.Collections}}|url=https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html|website=Java Platform Standard Edition 8 Documentation|publisher=[[Oracle Corporation]]|accessdate=1 May 2016}}&lt;/ref&gt;
 * மைக்ரோசாப்டின் .NET Framework 2.0 பதிப்பு இருமத் தேடல் அல்கோரித வகைகளைத் தனது  அடிப்படைத் திரட்டு வகைகளாகத் தருகிறது. எடுத்துகாட்டு: &lt;code&gt;System.Array&lt;/code&gt; எனும் முறை, &lt;code&gt;இருமத் தேடல்&lt;T&gt;(T[] அணி, T மதிப்பு)&lt;/code&gt;.&lt;ref&gt;{{cite web|title=List&lt;T&gt;.இருமத் தேடல் முறை (T)|url=https://msdn.microsoft.com/en-us/library/w4e7fxsh%28v=vs.110%29.aspx|website=Microsoft Developer Network|accessdate=10 April 2016}}&lt;/ref&gt;
 * பைத்தான் நிரலாக்க மொழி  &lt;code&gt;இருமப்பகுப்பு&lt;/code&gt; எனும் முறையை இருமத் தேடலுக்காகத் தருகிறது.&lt;ref&gt;{{cite web|title=8.6. bisect — Array bisection algorithm|url=https://docs.python.org/3.6/library/bisect.html#module-bisect|website=The Python Standard Library|publisher=Python Software Foundation|accessdate=26 March 2018}}&lt;/ref&gt;
 * உரூபி நிரலாக்க மொழியின் அணி வகுப்பு &lt;code&gt;bsearch&lt;/code&gt; எனும் முறையை உள்கட்டமைப்பாகவும் தோராய இணைசேர்ப்பாகவும் உள்ளடக்கியுள்ளது.{{Sfn|Fitzgerald|2007|p=152}}
 
 * Go நிரலாக்க மொழியின் &lt;code&gt;sort&lt;/code&gt; எனும் செந்தர நூலகத் தொகுப்பு &lt;code&gt;Search&lt;/code&gt;, &lt;code&gt;SearchInts&lt;/code&gt;, &lt;code&gt;SearchFloat64s&lt;/code&gt;, and &lt;code&gt;SearchStrings&lt;/code&gt;,ஆகிய பொது இருமத் தேடல் முறையையும் முழு எண்களின் பிரிவுகளையும் தெப்பப் புள்ளி எண்களையும் சரங்களையும் தேடும் குறிப்பிட்ட நடைமுறைகளையும் கொண்டுள்ளது.&lt;ref&gt;{{cite web | work = The Go Programming Language | url = http://golang.org/pkg/sort/ | title = Package {{mono|sort}} |accessdate=28 April 2016}}&lt;/ref&gt;
 
 * Objective-C மொழியில் கக்கோவா (Cocoa) சட்டகம் the &lt;code&gt;[https://developer.apple.com/library/mac/documentation/Cocoa/Reference/Foundation/Classes/NSArray_Class/NSArray.html#//apple_ref/occ/instm/NSArray/indexOfObject:inSortedRange:options:usingComparator: NSArray -indexOfObject:inSortedRange:options:usingComparator:]&lt;/code&gt; எனும் இருமத் தேடல் முறையை Mac OS X 10.6+ இல் தருகிறது.&lt;ref&gt;{{cite web|title={{mono|NSArray}}|url=https://developer.apple.com/library/mac/documentation/Cocoa/Reference/Foundation/Classes/NSArray_Class/index.html#//apple_ref/occ/instm/NSArray/indexOfObject:inSortedRange:options:usingComparator:|website=Mac Developer Library|publisher=[[Apple Inc.]]|accessdate=1 May 2016}}&lt;/ref&gt; ஆப்பிளின் Core Foundation C மொழியின் சட்டகமும் கூட  &lt;code&gt;[https://developer.apple.com/library/mac/documentation/CoreFoundation/Reference/CFArrayRef/Reference/reference.html#//apple_ref/c/func/CFArrayBSearchValues CFArrayBSearchValues()]&lt;/code&gt; எனும் இருமத் தேடல் சார்பைப் பெற்றுள்ளது.&lt;ref&gt;{{cite web|title={{mono|CFArray}}|url=https://developer.apple.com/library/mac/documentation/CoreFoundation/Reference/CFArrayRef/index.html#//apple_ref/c/func/CFArrayBSearchValues|website=Mac Developer Library|publisher=[[Apple Inc.]]|accessdate=1 May 2016}}&lt;/ref&gt;
 
 ==குறிப்புகளும் மேற்கோள்களும்==
 
 === குறிப்புகள் ===
 {{Notelist}}
 
 === மேற்கோள்கள் ===
 {{Reflist|30em}}
 
 === நூல்கள் ===
 {{columns-list|2|style=font-size:90%;|
 * {{cite book|last1=Alexandrescu|first1=Andrei|title=The D Programming Language|date=2010|publisher=Addison-Wesley Professional|location=Upper Saddle River, NJ|isbn=0-321-63536-1|ref=harv}}
 * {{cite book
 | last = Bentley
 | first = Jon
 | authorlink = Jon Bentley (computer scientist)
 | title = Programming Pearls
 | edition = 2nd
 | publisher = [[Addison-Wesley]]
 | year = 2000
 | origyear = 1986
 | isbn = 0-201-65788-0|ref=harv}}
 *{{cite book|last1=Butterfield|first1=Andrew|last2=Ngondi|first2=Gerard E.|title=A Dictionary of Computer Science|url=https://archive.org/details/isbn_9780199688975|date=2016|publisher=[[ஒக்ஸ்போர்ட் பல்கலைக்கழகப் பதிப்பகம்]]|location=Oxford, UK|isbn=978-0199688975|edition=7th|ref=harv}}
 * {{cite book | title=Data Structures and Algorithms | publisher=[[வேர்ல்டு சயின்டிபிக்]] | last1=Chang|first1=Shi-Kuo| year=2003 | location=Singapore | isbn=978-981-238-348-8 | volume=13 | work=Software Engineering and Knowledge Engineering|ref=harv}}
 * {{Introduction to Algorithms|edition=3|ref=harv}}
 * {{cite book|last1=Fitzgerald|first1=Michael|title=Ruby Pocket Reference|date=2007|publisher=[[O'Reilly Media]]|location=[[Sebastopol, California|Sebastopol, CA]]|isbn=978-1-4919-2601-7|ref=harv}}
 * {{cite book|last1=Goldman|first1=Sally A.|last2=Goldman|first2=Kenneth J.|title=A Practical Guide to Data Structures and Algorithms using Java|date=2008|publisher=[[CRC Press]]|location=Boca Raton|isbn=978-1-58488-455-2|ref=harv}}
 * {{TAOCP|volume=1|edition=3|harv=y}} {{ISBN|0-201-89683-4}}.
 * {{TAOCP|volume=3|edition=2|harv=y}} {{ISBN|0-201-89685-0}}.
 * {{TAOCP|volume=4a|edition=1|harv=y}} {{ISBN|0-201-03804-8}}.
 * {{cite book|last1=Leiss|first1=Ernst|title=A Programmer's Companion to Algorithm Analysis|url=https://archive.org/details/programmerscompa0000leis|date=2007|publisher=CRC Press|location=Boca Raton, FL|isbn=1-58488-673-0|ref=harv}}
 * {{cite book|last1=Moffat|first1=Alistair|last2=Turpin|first2=Andrew|title=Compression and Coding Algorithms|url=https://archive.org/details/compressioncodin0000moff|date=2002|publisher=Kluwer Academic Publishers|location=Hamburg, Germany|isbn=978-0-7923-7668-2|ref=harv|doi=10.1007/978-1-4615-0935-6}}
 * {{cite book|last1=Sedgewick|first1=Robert|last2=Wayne|first2=Kevin|authorlink1=Robert Sedgewick (computer scientist)|title=Algorithms|date=2011|publisher=Addison-Wesley Professional|location=Upper Saddle River, NJ|isbn=978-0-321-57351-3|edition=4th|ref=harv|url=http://algs4.cs.princeton.edu/home/}} Condensed web version: {{open access}}; book version {{closed access}}.
 * {{cite book|last1=Stroustrup|first1=Bjarne|authorlink=Bjarne Stroustrup|title=The C++ Programming Language|edition=4th|date=2013|publisher=Addison-Wesley Professional|location=Upper Saddle River, NJ|isbn=978-0-321-56384-2|ref=harv}}
 }}
 
 ==வெளி இணைப்புகள்==
 {{Wikibooks|Algorithm implementation|Search/Binary search|Binary search}}
 * [https://xlinux.nist.gov/dads/HTML/binarySearch.html NIST Dictionary of Algorithms and Data Structures: binary search]
 
 [[பகுப்பு:தேடல் அல்கோரிதங்கள்]]