இருமத் தேடல் அல்கோரிதம்
இக்கட்டுரையின் தலைப்பு விக்கிப்பீடியாவின் பெயரிடல் மரபுக்கோ, கலைக்களஞ்சிய பெயரிடல் மரபுக்கோ ஒவ்வாததாக இருக்கலாம் இக்கட்டுரையின் தலைப்பினை பெயரிடல் மரபுக்கு ஏற்றவாறு மாற்றக் கோரப்பட்டுள்ளது. உங்கள் கருத்துக்களை உரையாடல் பக்கத்தில் தெரிவியுங்கள். |
கணினி அறிவியலில், இருமத் தேடல், அல்லது அரை-இடைவெளித் தேடல்,[1] மடக்கைத் தேடல்,[2] அல்லது இருமத் தறித்தல்,[3] என்பது ஒரு தேடல் அலகோரிதம் அல்லது தேடல் படிமுறைத் தீர்வாகும். இது குறிப்பிட்ட தேர்ந்தெடுத்த அணிக்குள் இலக்கு மதிப்பு இருப்பிட்த்தைக் கண்டுபிடித்தலாகும்.[4][5] இருமத் தேடல் இலக்கு மதிப்பை அணியின் நடு உறுப்போடு ஒப்பிடுகிறது; அவை சமமாக அமையாவிட்டால், இலக்கு மதிப்பு அமையமுடியாத அரைப்பகுதி நீக்கப்படும்; தேடல் எஞ்சிய அரைப்ப்பகுதியில் வெற்றி கிடைக்கும் வரை தொடரும். எஞ்சிய அரைப்பகுதியில் வெற்றாகத் தேடல் முடிவுற்றால், அந்த அணிக்குள் இலக்கு மதிப்பு இல்லை என்று பொருள்.
இருமத் தேடல் அரிய மடக்கை நேரத்தில், O(log n) இன் ஒப்பீடுகளைச் செய்து செயல்படுகிறது. இங்கு, n என்பது அணியில் அமையும் உறுப்புகளின் எண்ணிக்கை ஆகும்; O என்பது பேரெழுத்து O சார்ந்த குறிமானம் ஆகும் ; log என்பது மடக்கையாகும். இருமத் தேடல் நிலையான (O(1)) வெளியை எடுத்துக் கொள்கிறது; இதன் பொருள், அணியில் உள்ள உறுப்புகளின் எண்ணிக்கை மாறுபட்டாலும் அல்கோரிதத்தில் அதற்காக அமையும் வெளி ஒரே அளவாகவே அமையும் என்பதாகும்.[6] விரைவுப் பட்டியல் போன்ற விரைவாகத் தேடும் சிறப்புத் தரவுக் கட்டமைப்புகள் இருந்தாலும், இருமத் தேடல் அகல்நெடுக்கமான பல பயன்பாட்டுச் சிக்கல்களுக்கு ஏற்றதானதாக உள்ளது.
இந்த எண்ணக்கரு எளியதாகத் தோன்றினாலும், சரியாக இருமத் தேடலை நடைமுறைப்படுத்த, அவற்றின் நடுப்புள்ளியைக் கணக்கிடுவதிலும் கணிப்பு முடித்து வெளியேறும் நிலைமைகளிலும் நிலவும் சில நுட்பங்களில் கவனம் செலுத்த வேண்டிய தேவைகள் உள்ளன.
இருமத் தேடலில் பல வேறுபாடுள்ள முறைகள் உள்ளன. குறிப்பாக பகுதி ஓடையாக்க முறை, ஒரே இலக்கு மதிப்புக்கு பல அணிகளில் தேடுவதால் இருமத் தேடல்களின் வேகத்தைக் கூட்டுகிறது; கணிப்பு வடிவவியலிலும் எண்ணற்ற பிற புலங்களிலும் உள்ள தேடல் சிக்கலகளுக்குத் திறமையான தீர்வுகளை காண்கிறது. படியேற்ற முறைத் தேடல் இருமத் தேடலை வரம்பற்ர பட்டியல்களுக்கு விரிவாக்குகிறது. இருமத் தேடல் தருவும் B-தருவும் சார்ந்த தரவுக் கட்டமைப்புகள் இருமத் ஹ்டேடலைச் சார்ந்தவையே.
படிமுறைத் தீர்வு (அல்கோரிதம்)
தொகுஇருமத் தேடல் வரிசையான உறுப்புகள் அமைந்த அணிகளில் வேலை செய்கிறது. இலக்கு மதிப்பை அணியின் நடு உறுப்புடன் ஒப்பிடுவதன் வாயிலாக தன் தேடலை இருமத் தேடல் தொடங்குகிறது. இலக்கு மதிப்பும் நடு உறுப்பு மதிப்பும் ஒன்றினால் அணியின் இருப்பு தீர்மானமாகித் தேடல் முடிவடைகிறது. நடுவுறுப்பின் மதிப்புக்கு இலக்கு மதிப்பு குறைவாகவோ கூடுதலாகவோ இருந்தால், தேடல் முறையே அணியின் கீழ் அல்லது மேல் அரைப்பகுதியில், மற்ற அரைப்பகுதியைத் தவிர்த்துவிட்டு, தேடலைத் தொடர்கிறது .[7]
வழிமுறை
தொகுA0 ≤ A1 ≤ ... ≤ An−1 என்ற முறையில் வரிசை படுத்தப்பட்ட, A0, A1, ..., An−1 எனும் உறுப்பு மதிப்புகளை/பதிவுகளைக் கொண்ட n உறுப்புகள் அமைந்த A அணியைக் கருதுவோம். தேடும் இலக்கு மதிப்பு T எனில், பின்வரும் இயல்நிரல் A அணியில் அமைந்த T சுட்டியைக் கண்டுபிடிக்கும் இருமத் தேடலை நிகழ்த்துகிறது.[7]
- L மதிப்பு 0 எனில், மேலும் R மதிப்பு n எனில், − 1.
- L மதிப்பு > R எனில், தேடல் தோல்வியில் முடிகிறது.
- m (நடு உறுப்பின் இருப்பு) மதிப்பை (L + R) / 2 எனும் தரை மதிப்பாகக் ( முந்தைய மிகப் பெரிய எண்) கொள்க.
- Am < T எனில், L மதிப்பை m + 1 ஆகக் கொண்டு இரண்டாம் படிநிலைக்குச் செல்க.
- Am > T எனில், R மதிப்பை m − 1 ஆகக் கொண்டு இரண்டாம் படிநிலைக்குச் செல்க.
- இப்போது Am = T எனில், தேடல் முடிந்தது; m மதிப்புக்கு மீள்க.
இந்த திருபத் திரும்ப பலமுறை செய்யும் வழிமுறை (பன்னிச் செயல்முறை-iteration) இரு மாறிகளின் தேடல் வரம்புகளைக் கண்காணித்துக் கொள்கிறது.
நூலக உதவி
தொகுபல நிரலாக்க மொழிக்கான செந்தர நூலகங்களில் இருமத் தேடல் அல்கோரித இயல்நிரல்கள் உள்ளன:
- C நிரலாக்க மொழி, இதற்கான சார்பைத் (இயல்நிரலைத்)
bsearch()எனும் தனது C செந்தர நூலகத்தில் தருகிறது. இந்நிரல் இருமத் தேடல் வழியிலேயே நடைமுறைப்படுத்தப்படுகிறது. என்றாலும் அதன் அலுவல்முறைப் பதிப்பில் இது வேண்டப்படுவதில்லை.[8] - C++ மொழியின் செந்தர வார்ப்புரு நூலகமும்
இருமத் தேடல்()சார்ந்தகீழ் வரம்பு(),மேல் வரம்பு(),சம நெடுக்கம்()ஆகிய சார்புகளைத் தருகிறது.[9] - கோபால்(COBOL) மொழி, கோபால் வரிசை அட்டவணைகளில் இருமத் தேடலை நிகழ்த்துவதற்கான
தேடு அனைத்தும்எனும் வினையைத் தருகிறது.[10] - ஜாவா நிரலாக்க மொழி, ஜாவா அணிகளிலும் பட்டியல்களிலும் இருமத் தேடலை நிகழ்த்தும் மிகைச்சுமையுள்ள
இருமத் தேடல்()சார்ந்த நிலையியல் முறைகளின் கணத்தை[[[:வார்ப்புரு:Javadoc:SE/Home URL]]docs/api/java/util/Arrays.html Arrays],[[[:வார்ப்புரு:Javadoc:SE/Home URL]]docs/api/java/util/Collections.html Collections]ஆகிய வகைகளில் தனது செந்தரjava.utilதொகுப்பில் தருகிறது.[11][12] - மைக்ரோசாப்டின் .NET Framework 2.0 பதிப்பு இருமத் தேடல் அல்கோரித வகைகளைத் தனது அடிப்படைத் திரட்டு வகைகளாகத் தருகிறது. எடுத்துகாட்டு:
System.Arrayஎனும் முறை,இருமத் தேடல்<T>(T[] அணி, T மதிப்பு).[13] - பைத்தான் நிரலாக்க மொழி
இருமப்பகுப்புஎனும் முறையை இருமத் தேடலுக்காகத் தருகிறது.[14] - உரூபி நிரலாக்க மொழியின் அணி வகுப்பு
bsearchஎனும் முறையை உள்கட்டமைப்பாகவும் தோராய இணைசேர்ப்பாகவும் உள்ளடக்கியுள்ளது.[15]
- Go நிரலாக்க மொழியின்
sortஎனும் செந்தர நூலகத் தொகுப்புSearch,SearchInts,SearchFloat64s, andSearchStrings,ஆகிய பொது இருமத் தேடல் முறையையும் முழு எண்களின் பிரிவுகளையும் தெப்பப் புள்ளி எண்களையும் சரங்களையும் தேடும் குறிப்பிட்ட நடைமுறைகளையும் கொண்டுள்ளது.[16]
- Objective-C மொழியில் கக்கோவா (Cocoa) சட்டகம் the
NSArray -indexOfObject:inSortedRange:options:usingComparator:எனும் இருமத் தேடல் முறையை Mac OS X 10.6+ இல் தருகிறது.[17] ஆப்பிளின் Core Foundation C மொழியின் சட்டகமும் கூடCFArrayBSearchValues()எனும் இருமத் தேடல் சார்பைப் பெற்றுள்ளது.[18]
குறிப்புகளும் மேற்கோள்களும்
தொகுகுறிப்புகள்
தொகுமேற்கோள்கள்
தொகு- ↑ (1975) "A modification to the half-interval search (binary search) method". {{{booktitle}}}, 95–101. DOI:10.1145/503561.503582.
- ↑ Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Binary search".
- ↑ Butterfield & Ngondi 2016.
- ↑ Cormen et al. 2009, ப. 39.
- ↑ Weisstein, Eric W., "Binary Search", MathWorld.
- ↑ Flores, Ivan; Madpis, George (1971). "Average binary search length for dense ordered lists". Communications of the ACM 14 (9): 602–603. doi:10.1145/362663.362752.
- ↑ 7.0 7.1 Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Algorithm B".
- ↑ "bsearch – binary search a sorted table". The Open Group Base Specifications (7th ed.). The Open Group. 2013. பார்க்கப்பட்ட நாள் 28 March 2016.
- ↑ Stroustrup 2013, §32.6.1 ("Binary Search").
- ↑ Unisys (2012), COBOL ANSI-85 Programming Reference Manual, vol. 1, pp. 598–601
- ↑ "java.util.Arrays". Java Platform Standard Edition 8 Documentation. Oracle Corporation. பார்க்கப்பட்ட நாள் 1 May 2016.
{{cite web}}: templatestyles stripmarker in|title=at position 1 (help) - ↑ "java.util.Collections". Java Platform Standard Edition 8 Documentation. Oracle Corporation. பார்க்கப்பட்ட நாள் 1 May 2016.
{{cite web}}: templatestyles stripmarker in|title=at position 1 (help) - ↑ "List<T>.இருமத் தேடல் முறை (T)". Microsoft Developer Network. பார்க்கப்பட்ட நாள் 10 April 2016.
- ↑ "8.6. bisect — Array bisection algorithm". The Python Standard Library. Python Software Foundation. பார்க்கப்பட்ட நாள் 26 March 2018.
- ↑ Fitzgerald 2007, ப. 152.
- ↑ "Package sort". The Go Programming Language. பார்க்கப்பட்ட நாள் 28 April 2016.
{{cite web}}: templatestyles stripmarker in|title=at position 9 (help) - ↑ "NSArray". Mac Developer Library. Apple Inc. பார்க்கப்பட்ட நாள் 1 May 2016.
{{cite web}}: templatestyles stripmarker in|title=at position 1 (help) - ↑ "CFArray". Mac Developer Library. Apple Inc. பார்க்கப்பட்ட நாள் 1 May 2016.
{{cite web}}: templatestyles stripmarker in|title=at position 1 (help)
நூல்கள்
தொகு- Alexandrescu, Andrei (2010). The D Programming Language. Upper Saddle River, NJ: Addison-Wesley Professional. பன்னாட்டுத் தரப்புத்தக எண் 0-321-63536-1.
{{cite book}}: Invalid|ref=harv(help) - Bentley, Jon (2000) [1986]. Programming Pearls (2nd ed.). Addison-Wesley. பன்னாட்டுத் தரப்புத்தக எண் 0-201-65788-0.
{{cite book}}: Invalid|ref=harv(help) - Butterfield, Andrew; Ngondi, Gerard E. (2016). A Dictionary of Computer Science (7th ed.). Oxford, UK: ஒக்ஸ்போர்ட் பல்கலைக்கழகப் பதிப்பகம். பன்னாட்டுத் தரப்புத்தக எண் 978-0199688975.
{{cite book}}: Invalid|ref=harv(help) - Chang, Shi-Kuo (2003). Data Structures and Algorithms. Vol. 13. Singapore: வேர்ல்டு சயின்டிபிக். பன்னாட்டுத் தரப்புத்தக எண் 978-981-238-348-8.
{{cite book}}:|work=ignored (help); Invalid|ref=harv(help) - வார்ப்புரு:Introduction to Algorithms
- Fitzgerald, Michael (2007). Ruby Pocket Reference. Sebastopol, CA: O'Reilly Media. பன்னாட்டுத் தரப்புத்தக எண் 978-1-4919-2601-7.
{{cite book}}: Invalid|ref=harv(help) - Goldman, Sally A.; Goldman, Kenneth J. (2008). A Practical Guide to Data Structures and Algorithms using Java. Boca Raton: CRC Press. பன்னாட்டுத் தரப்புத்தக எண் 978-1-58488-455-2.
{{cite book}}: Invalid|ref=harv(help) - வார்ப்புரு:TAOCP பன்னாட்டுத் தரப்புத்தக எண் 0-201-89683-4.
- வார்ப்புரு:TAOCP பன்னாட்டுத் தரப்புத்தக எண் 0-201-89685-0.
- வார்ப்புரு:TAOCP பன்னாட்டுத் தரப்புத்தக எண் 0-201-03804-8.
- Leiss, Ernst (2007). A Programmer's Companion to Algorithm Analysis. Boca Raton, FL: CRC Press. பன்னாட்டுத் தரப்புத்தக எண் 1-58488-673-0.
{{cite book}}: Invalid|ref=harv(help) - Moffat, Alistair; Turpin, Andrew (2002). Compression and Coding Algorithms. Hamburg, Germany: Kluwer Academic Publishers. எண்ணிம ஆவணச் சுட்டி:10.1007/978-1-4615-0935-6. பன்னாட்டுத் தரப்புத்தக எண் 978-0-7923-7668-2.
{{cite book}}: Invalid|ref=harv(help) - Sedgewick, Robert; Wayne, Kevin (2011). Algorithms (4th ed.). Upper Saddle River, NJ: Addison-Wesley Professional. பன்னாட்டுத் தரப்புத்தக எண் 978-0-321-57351-3.
{{cite book}}: Invalid|ref=harv(help) Condensed web version:
; book version வார்ப்புரு:Closed access. - Stroustrup, Bjarne (2013). The C++ Programming Language (4th ed.). Upper Saddle River, NJ: Addison-Wesley Professional. பன்னாட்டுத் தரப்புத்தக எண் 978-0-321-56384-2.
{{cite book}}: Invalid|ref=harv(help)
வெளி இணைப்புகள்
தொகு