பைனரி தேடல் ஒரு வரிசையில் ஒரு உறுப்பு கண்டுபிடிக்க எளிதான வழிகளில் ஒன்றாகும்

பெரும்பாலும், புரோகிராமர்கள், ஆரம்பிக்கிறவர்கள், ஒரு குறிப்பிட்ட எண்ணை கண்டுபிடிப்பது அவசியமான எண்களின் தொகுப்பாக உள்ளது என்ற உண்மையை எதிர்கொள்கின்றனர். இந்த தொகுப்பு வரிசை எனப்படுகிறது. அதில் சரியான உறுப்பு கண்டுபிடிக்க, நிறைய வழிகள் உள்ளன. ஆனால் அவர்களில் எளிமையானது பைனரி தேடலாகும். முறை என்ன? பைனரி தேடலை எப்படி செயல்படுத்த வேண்டும்? பாஸ்கல் அத்தகைய ஒரு திட்டத்தை ஏற்பதற்கு எளிய சூழலாக இருக்கிறது, எனவே படிப்பதற்காக அதைப் பயன்படுத்துவோம்.

முதலில், இந்த முறையின் நன்மைகள் என்னவென்பதை ஆராய்வோம், எல்லாவற்றிற்கும் பின்னர், நாம் புரிந்து கொள்ள முடியும், இந்த தலைப்பைப் படிப்பதில் என்ன இருக்கிறது. எனவே, குறைந்தது 100000000 கூறுகளின் ஒரு பரிமாணத்தை கொண்ட ஒரு வரிசை உள்ளது, அதில் நீங்கள் ஒரு குறிப்பிட்ட ஒன்றை கண்டுபிடிக்க வேண்டும். நிச்சயமாக, இந்த சிக்கல் எளிதாக ஒரு எளிமையான நேர்கோட்டு தேடல் மூலம் தீர்க்கப்பட முடியும், இதில் நாம் வரிசையில் உள்ள அனைத்தையும் விரும்பிய உறுப்பை ஒப்பிட்டு ஒரு வட்டத்திற்கு பயன்படுத்துவோம். பிரச்சனை இந்த யோசனை செயல்படுத்த அதிக நேரம் எடுக்கும் என்று. பல நடைமுறைகளுக்கான எளிய பாஸ்கல் திட்டத்தில் மற்றும் பிரதான உரையின் மூன்று வரிகளுடன், நீங்கள் அதை கவனிக்க மாட்டீர்கள், ஆனால் நீங்கள் அதிகமான அல்லது குறைவான பெரிய திட்டங்களை கிளைக்கிங் மற்றும் நல்ல செயல்பாட்டுடன் தொடங்கும்போது, முடிந்த நிரல் நீண்ட நேரம் ஏற்றப்படும். கணினி மோசமான செயல்திறன் கொண்டது குறிப்பாக. எனவே, பைனரி தேடலைக் காணலாம், இது தேடல் நேரத்தை குறைந்தது இரண்டு முறை குறைக்கிறது.

எனவே, இந்த முறையின் கொள்கை என்ன? உடனடியாக அது பைனரி தேடல் எந்த வரிசையில் இல்லை என்று சொல்ல பயனுள்ளது, ஆனால் எண்கள் ஒரு வரிசைப்படுத்தப்பட்ட தொகுப்பில் மட்டும். ஒவ்வொரு அடுத்த படியிலும், வரிசையின் சராசரி உறுப்பு எடுக்கப்பட்டது (உறுப்பு எண்ணைக் குறிப்பிடுகிறது). சராசரி எண்ணிக்கையை விட அதிகமாக இருந்தால், இடதுபுறத்தில் இருக்கும் எல்லாவற்றையும் விட சராசரி உறுப்பு விட குறைவாக இருக்கும், அதைத் தேட முடியாது, அங்கு தேட முடியாது. மாறாக, சராசரியை விட குறைவாக இருந்தால், வலதுபுற எண்கள் மத்தியில், நீங்கள் அவற்றைப் பார்க்க முடியாது. அடுத்து, ஒரு புதிய தேடல் பகுதியை நாங்கள் தேர்வு செய்வோம், முதல் உறுப்பு முழு வரிசையின் நடுத்தர உறுப்பு இருக்கும், கடைசியாக கடைசியாக ஒன்று இருக்கும். புதிய பகுதியின் சராசரி எண்ணிக்கை ¼ மொத்த பிரிவில் இருக்கும், அதாவது (கடைசி உறுப்பு + முழு வரிசைகளின் சராசரி உறுப்பு) / 2 ஆகும். மீண்டும், அதே செயல்பாடு செய்யப்படுகிறது - வரிசையின் சராசரி எண்ணிக்கையுடன் ஒப்பிடுக. தேவையான மதிப்பு சராசரியை விட குறைவாக இருந்தால், வலது புறத்தை நிராகரிக்கவும், மேலும் இந்த நடுத்தர உறுப்பு காணும் வரையில் வரை இதைச் செய்யவும்.

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

இது "massive" எனப்படும் 1 "h" என்ற ஒரு வரிசைக்கு, "niz" என்றழைக்கப்படும் ஒரு உயர்மட்ட தேடல் எல்லைகளைக் குறிக்கும் மாறி, "verh" என்றழைக்கப்படும் ஒரு மேல் உள்ளீடு, நடுத்தர தேடல் உறுப்பு "sredn"; தேவையான எண் "isk" ஆகும்.

எனவே, தேடல் இடைவெளியின் மேல் மற்றும் கீழ் எல்லைகளை முதலில் ஒதுக்கவும்:

நிஜம்: = 1;
சரி: = h + 1;

பின் நாம் சுழற்சியை ஏற்பாடு செய்கிறோம், "கீழே மேல்மட்டத்தை விட குறைவானது":

இல்லையெனில் தொடங்கும்

ஒவ்வொரு படியிலும், பிரிவு 2 ஐ பிரித்து:

ஸ்ரேட்: = (niz + verh) div 2; {Div எஞ்சியுள்ளதைப் பகிர்வதால்,

ஒவ்வொரு முறையும் நாம் ஒரு காசோலை நடத்துகிறோம். சராசரியாக விரும்பிய ஒரு சமமாக இருந்தால், நாம் சுழற்சியில் குறுக்கிடுவோம், ஏனெனில் தேவையான உறுப்பு ஏற்கனவே காணப்படுவதால்:

Sredn = isk பின்னர் break;

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

Massiv [sredn]> isk என்றால் verh: = sredn;

அதற்கு மாறாக, நாம் அதை கீழ்த்தரமான எல்லைகளாக ஆக்குகிறோம்:

வேறு: = sredn;
முடிவுக்கு;

அதுதான் அந்த நிகழ்ச்சியில் இருக்கும்.

பைனரி முறை நடைமுறையில் எவ்வாறு இருக்கும் என்பதை ஆய்வு செய்வோம். 1, 3, 5, 7, 10, 12, 18 போன்ற வரிசைகளை எடுக்கவும்.

மொத்தத்தில், நமக்கு 7 உறுப்புகள் உள்ளன, எனவே சராசரி நான்காவது, அதன் மதிப்பு 7 ஆகும்.

12 க்கும் மேற்பட்ட 7 க்கும் அதிகமானதால், 1,3 மற்றும் 5 கூறுகள் நிராகரிக்கப்படலாம். அடுத்து, 4 எண்கள் உள்ளன, 4/2 மீதமுள்ளவை 2 ஆகும். எனவே, புதிய நடுத்தர உறுப்பு 10 ஆக இருக்கும்.

12 ஆனது 10 க்கும் அதிகமானதாக இருப்பதால், நாங்கள் 7 ஐ நிராகரிக்கிறோம். 10, 12 மற்றும் 18 மட்டுமே உள்ளன.

இங்கே மத்திய உறுப்பு 12 ஆனது, இது தேவையான எண். பணி நிறைவடைந்தது - எண் 12 காணப்படுகிறது.