இருமத் தேடல் அல்கோரிதம்

கட்டற்ற கலைக்களஞ்சியமான விக்கிப்பீடியாவில் இருந்து.
Jump to navigation Jump to search

கணினி அறிவியலில், இருமத் தேடல், அல்லது அரை-இடைவெளித் தேடல்,[1] மடக்கைத் தேடல்,[2] அல்லது இருமத் தறித்தல்,[3] என்பது ஒரு தேடல் அலகோரிதம் அல்லது தேடல் படிமுறைத் தீர்வாகும். இது குறிப்பிட்ட தேர்ந்தெடுத்த அணிக்குள் இலக்கு மதிப்பு இருப்பிட்த்தைக் கண்டுபிடித்தலாகும்.[4][5] இருமத் தேடல் இலக்கு மதிப்பை அணியின் நடு உறுப்போடு ஒப்பிடுகிறது; அவை சமமாக அமையாவிட்டால், இலக்கு மதிப்பு அமையமுடியாத அரைப்பகுதி நீக்கப்படும்; தேடல் எஞ்சிய அரைப்ப்பகுதியில் வெற்றி கிடைக்கும் வரை தொடரும். எஞ்சிய அரைப்பகுதியில் வெற்றாகத் தேடல் முடிவுற்றால், அந்த அணிக்குள் இலக்கு மதிப்பு இல்லை என்று பொருள்.

இருமத் தேடல் அரிய மடக்கை நேரத்தில், O(log n) இன் ஒப்பீடுகளைச் செய்து செயல்படுகிறது. இங்கு, n என்பது அணியில் அமையும் உறுப்புகளின் எண்ணிக்கை ஆகும்; O என்பது பேரெழுத்து O சார்ந்த குறிமானம் ஆகும் ; log என்பது மடக்கையாகும். இருமத் தேடல் நிலையான (O(1)) வெளியை எடுத்துக் கொள்கிறது; இதன் பொருள், அணியில் உள்ள உறுப்புகளின் எண்ணிக்கை மாறுபட்டாலும் அல்கோரிதத்தில் அதற்காக அமையும் வெளி ஒரே அளவாகவே அமையும் என்பதாகும்.[6] விரைவுப் பட்டியல் போன்ற விரைவாகத் தேடும் சிறப்புத் தரவுக் கட்டமைப்புகள் இருந்தாலும், இருமத் தேடல் அகல்நெடுக்கமான பல பயன்பாட்டுச் சிக்கல்களுக்கு ஏற்றதானதாக உள்ளது.

இந்த எண்ணக்கரு எளியதாகத் தோன்றினாலும், சரியாக இருமத் தேடலை நடைமுறைப்படுத்த, அவற்றின் நடுப்புள்ளியைக் கணக்கிடுவதிலும் கணிப்பு முடித்து வெளியேறும் நிலைமைகளிலும் நிலவும் சில நுட்பங்களில் கவனம் செலுத்த வேண்டிய தேவைகள் உள்ளன.

இருமத் தேடலில் பல வேறுபாடுள்ள முறைகள் உள்ளன. குறிப்பாக பகுதி ஓடையாக்க முறை, ஒரே இலக்கு மதிப்புக்கு பல அணிகளில் தேடுவதால் இருமத் தேடல்களின் வேகத்தைக் கூட்டுகிறது; கணிப்பு வடிவவியலிலும் எண்ணற்ற பிற புலங்களிலும் உள்ள தேடல் சிக்கலகளுக்குத் திறமையான தீர்வுகளை காண்கிறது. படியேற்ற முறைத் தேடல் இருமத் தேடலை வரம்பற்ர பட்டியல்களுக்கு விரிவாக்குகிறது. இருமத் தேடல் தருவும் B-தருவும் சார்ந்த தரவுக் கட்டமைப்புகள் இருமத் ஹ்டேடலைச் சார்ந்தவையே.

படிமுறைத் தீர்வு (அல்கோரிதம்)[தொகு]

இருமத் தேடல் வரிசையான உறுப்புகள் அமைந்த அணிகளில் வேலை செய்கிறது. இலக்கு மதிப்பை அணியின் நடு உறுப்புடன் ஒப்பிடுவதன் வாயிலாக தன் தேடலை இருமத் தேடல் தொடங்குகிறது. இலக்கு மதிப்பும் நடு உறுப்பு மதிப்பும் ஒன்றினால் அணியின் இருப்பு தீர்மானமாகித் தேடல் முடிவடைகிறது. நடுவுறுப்பின் மதிப்புக்கு இலக்கு மதிப்பு குறைவாகவோ கூடுதலாகவோ இருந்தால், தேடல் முறையே அணியின் கீழ் அல்லது மேல் அரைப்பகுதியில், மற்ற அரைப்பகுதியைத் தவிர்த்துவிட்டு, தேடலைத் தொடர்கிறது .[7]

வழிமுறை[தொகு]

A0A1 ≤ ... ≤ An−1 என்ற முறையில் வரிசை படுத்தப்பட்ட, A0, A1, ..., An−1 எனும் உறுப்பு மதிப்புகளை/பதிவுகளைக் கொண்ட n உறுப்புகள் அமைந்த A அணியைக் கருதுவோம். தேடும் இலக்கு மதிப்பு T எனில், பின்வரும் இயல்நிரல் A அணியில் அமைந்த T சுட்டியைக் கண்டுபிடிக்கும் இருமத் தேடலை நிகழ்த்துகிறது.[7]

  1. L மதிப்பு 0 எனில், மேலும் R மதிப்பு n எனில், − 1.
  2. L மதிப்பு > R எனில், தேடல் தோல்வியில் முடிகிறது.
  3. m (நடு உறுப்பின் இருப்பு) மதிப்பை (L + R) / 2 எனும் தரை மதிப்பாகக் ( முந்தைய மிகப் பெரிய எண்) கொள்க.
  4. Am < T எனில், L மதிப்பை m + 1 ஆகக் கொண்டு இரண்டாம் படிநிலைக்குச் செல்க.
  5. Am > T எனில், R மதிப்பை m − 1 ஆகக் கொண்டு இரண்டாம் படிநிலைக்குச் செல்க.
  6. இப்போது 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, and SearchStrings,ஆகிய பொது இருமத் தேடல் முறையையும் முழு எண்களின் பிரிவுகளையும் தெப்பப் புள்ளி எண்களையும் சரங்களையும் தேடும் குறிப்பிட்ட நடைமுறைகளையும் கொண்டுள்ளது.[16]
  • Objective-C மொழியில் கக்கோவா (Cocoa) சட்டகம் the NSArray -indexOfObject:inSortedRange:options:usingComparator: எனும் இருமத் தேடல் முறையை Mac OS X 10.6+ இல் தருகிறது.[17] ஆப்பிளின் Core Foundation C மொழியின் சட்டகமும் கூட CFArrayBSearchValues() எனும் இருமத் தேடல் சார்பைப் பெற்றுள்ளது.[18]

குறிப்புகளும் மேற்கோள்களும்[தொகு]

குறிப்புகள்[தொகு]

மேற்கோள்கள்[தொகு]

  1. (1975) "A modification to the half-interval search (binary search) method". {{{booktitle}}}, 95–101. DOI:10.1145/503561.503582.
  2. Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Binary search".
  3. Butterfield & Ngondi 2016.
  4. Cormen மற்றும் சிலர் 2009, பக். 39.
  5. Weisstein, Eric W., "Binary Search", MathWorld.
  6. 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. 7.0 7.1 Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Algorithm B".
  8. "bsearch – binary search a sorted table". The Open Group (2013). பார்த்த நாள் 28 March 2016.
  9. Stroustrup 2013, §32.6.1 ("Binary Search").
  10. Unisys (2012), COBOL ANSI-85 Programming Reference Manual, 1, pp. 598–601
  11. "java.util.Arrays". Oracle Corporation. பார்த்த நாள் 1 May 2016.
  12. "java.util.Collections". Oracle Corporation. பார்த்த நாள் 1 May 2016.
  13. "List<T>.இருமத் தேடல் முறை (T)". பார்த்த நாள் 10 April 2016.
  14. "8.6. bisect — Array bisection algorithm". Python Software Foundation. பார்த்த நாள் 26 March 2018.
  15. Fitzgerald 2007, பக். 152.
  16. "Package sort". The Go Programming Language. பார்த்த நாள் 28 April 2016.
  17. "NSArray". Apple Inc.. பார்த்த நாள் 1 May 2016.
  18. "CFArray". Apple Inc.. பார்த்த நாள் 1 May 2016.

நூல்கள்[தொகு]

வெளி இணைப்புகள்[தொகு]