தேடல் முறைகளுக்கான நெறிமுறை

தேடல் முறைகளுக்கான நெறிமுறை

1. வரிசைமுறைத் தேடல்

வரிசைமுறைத் தேடல் அல்லது தொடர் தேடல் பட்டியலில் விரும்பும் உறுப்பைக் கண்டுபிடிக்கும் வரை அல்லது பட்டியல் முடியும் வரை வரிசையிலுள்ள ஒவ்வொரு உறுப்புகளையும் சரிபார்த்து, குறிப்பிட்ட மதிப்பைப் பட்டியலில் கண்டுபிடிக்கும் வழிமுறையாகும். பட்டியலை வரிசைப்படுத்த வேண்டிய தேவை இல்லை.

போலி குறிமுறை

1. for மடக்கினைப் பயன்படுத்தி அணியில் பயணித்தல்.

2. ஒவ்வொரு சுழற்சியிலும், இலக்கு மதிப்பை தற்போதைய மதிப்புடன் ஒப்பிடவும்.

O மதிப்புகள் பொருத்தமாக இருந்தால் அணியின் தற்போதைய சுட்டெண்ணைத் திருப்பி அனுப்பும்.

O மதிப்புகள் பொருந்தாவிட்டால் அணியில் அடுத்துள்ள உறுப்புக்கு சென்று விடும்.

3. பொருத்தம் எதுவும் இல்லையென்றால், -1 மதிப்பைத் திருப்பி அனுப்பும்.

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

எடுத்துக்காட்டு 1:

Input:values[] = {5,34,65,12,77,35}

target = 77

Output: 4

எடுத்துக்காட்டு 2:

Input:values[] = {101,392,1,54,32,22,90,93}

Target = 200

Output: 1 (not found)

2. இருமத் தேடல்

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

இருமத் தேடலுக்கான போலி குறிமுறை

1. மைய உறுப்பிலிருந்து தொடங்கவும்:

O இலக்கு மதிப்பும் அணியின் மைய உறுப்பும் நிகர் எனில் (i.e. அதாவது, மைய இலக்கு = உறுப்புகளின் எண்ணிக்கை /2) மைய உறுப்பின் சுட்டெண்ணைத் திருப்பி அனுப்பும்.

O நிகரில்லை என்றால், மைய உறுப்பை மதிப்போடு ஒப்பிடவும்,

O மைய சுட்டெண்ணிலுள்ள எண் இலக்கு மதிப்பை விட பெரியது எனில், மைய சுட்டெண்ணிற்கு வலப்புறம் உள்ள உறுப்புகளைத் தேர்ந்தெடுத்து படிநிலை -1லிருந்து தொடங்கவும்.

O மைய சுட்டெண்ணிலுள்ள எண் இலக்கு மதிப்பை விட சிறியது எனில் மைய சுட்டெண்ணிற்கு இடப்புறம் உள்ள உறுப்புகளைத் தேர்ந்தெடுத்து படிநிலை – 1 லிருந்து தொடங்கவும்.

2. பொருத்தமான தேடல் கண்டுபிடிக்கப்பட்டால், பொருந்திய உறுப்பின் சுட்டெண்ணைத் திருப்பி அனுப்பும்.

3. பொருத்தம் இல்லையெனில், -1 என்ற மதிப்பைத் திருப்பி அனுப்பும் அல்லது தேடல் நிறைவேற்றப்படவில்லை என்ற தகவலை அறிவிக்கவும்.

இருமத் தேடல் இயங்கும் கோட்பாடுகள்

இருமத்தேடலில் பயன்படும் அணி வரிசையாக்கம் செய்யப்பட்ட அணியாகயிருக்க வேண்டும். இருமத் தேடலைப் பயன்படுத்தி மதிப்பு 60-ன் இருப்பிடத்தைத் தேடுவதாக எடுத்துக்கொள்வோம்.

முதலில் நாம் அணியின் மைய உறுப்பை mid = low + (high - low) / 2 என்ற வாய்ப்பாட்டைப் பயன்படுத்தித் தீர்மானிக்க வேண்டும்.

இங்கு , 0 + (9 - 0 ) / 2 = 4 (4.5 யின் முழு மதிப்பு எடுத்துக்கொள்ளவும்). அதனால் அணியின் மையம் 4 ஆகும்.

இப்பொழுது நாம் 4-ம் சுட்டெண் இருப்பிடத்தில் சேமிக்கப்பட்ட மதிப்போடு தேடப்படும் மதிப்பை (அதாவது, 60) ஒப்பிடு செய்வோம். 4-ம் சுட்டெண் இருப்பிடத்தில் உள்ள மதிப்பான 50 என்பது, இது தேடப்படும் மதிப்பு கிடையாது. தேடப்படும் மதிப்பானது 50-விட அதிகமாக இருப்பதால்.

low மதிப்பை m + 1 என மாற்றி புதிய mid மதிப்பை மறுபடியும் கண்டுபிடிக்க வேண்டும்.

low = mid + 1

mid = low + (high - low) / 2

இப்பொழுது நமது mid மதிப்பு 7 ஆகும். நாம் இருப்பிடம் 7-ல் சேமிக்கப்பட்ட மதிப்பை இலக்கு மதிப்போடு (அதாவது 60) ஒப்பிடுவோம்.

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

எனவே, நாம் mid மதிப்பைத் திரும்பவும் கணக்கீடு செய்ய வேண்டும்.

high = mid-1

mid = low + (high - low)/2

தற்பொழுது midமதிப்பு 5 ஆகும்.

நாம் இருப்பிடம் 5-ல் உள்ள சேமிக்கப்பட்ட மதிப்பை இலக்கு மதிப்போடு ஒப்பீடு செய்வோம். இது ஒரு சரியான பொருத்தமாகும்.

இலக்கு மதிப்பு 60, இருப்பிடம் 5-ல் சேமிக்கப்பட்டுள்ளது என்ற நாம் முடிவு செய்கிறோம். எடுத்துக்காட்டாக, இலக்கு மதிப்பு 95 எனில், இந்த செயல்முறை - 1 என்ற மதிப்பைத் திருப்பி அனுப்பும்.