[இசை] 

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

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

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

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

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

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

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

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

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

எனவே செயல்முறை மீண்டும் அனுமதிக்க படிப்படியாக வைத்து நாம் சென்று என்ன நடக்கிறது டிராக். எனவே முதல் நாம் கணக்கிட செய்ய வேண்டும் தற்போதைய வரிசைக்கு இடையில். சரி, நாம் முதல், நாம் சொல்ல வேண்டும் அனைத்து, மதிப்பு 19 தேடும். நாம் எண் 19 கண்டுபிடிக்க முயற்சி. இந்த முதல் உறுப்பு வரிசை, குறியீட்டு பூஜ்யம் அமைந்துள்ளது இந்த கடைசி உறுப்பு வரிசை குறியீட்டெண் 14 அமைந்துள்ளது. எனவே நாம் அந்த தொடக்க மற்றும் முடிவு அழைக்கிறேன். 

நாம் இடையில் மூலம் கணக்கிட 0 பிளஸ் 2 வகுக்க 14 சேர்க்கும்; அழகான நேரடியான இடையில். நாம் என்று சொல்ல முடியாது இடையில் இப்போது 7 ஆகிறது. எனவே 15 நாம் தேடும் என்ன? இல்லை, அது இல்லை. நாம் 19 தேடும். ஆனால் நாம் 19 அதிகமாக உள்ளது என்று எனக்கு தெரியும் நாங்கள் நடுத்தர வயதில் கண்டறியப்பட்டது என்ன விட. 

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

இப்போது, நாம் மீண்டும் இந்த வழியாக செல்ல. நாம் புதிய இடையில் கணக்கிட. 8 பிளஸ் 14 2 11 ஆல் வகுக்க, 22 ஆகும். இந்த நாம் தேடும் என்ன? இல்லை, அது இல்லை. நாம் என்று ஒரு மதிப்பு தேடும் நாம் தான் கண்டுபிடிக்கப்பட்டது குறைவாக. எனவே நாம் மீண்டும் செல்கிறோம் மீண்டும் செயல்முறை. நாம் இறுதியில் புள்ளி மாற்ற போகிறோம் இடையில் இடது இருக்கும். எனவே புதிய இறுதியில் புள்ளி 10 ஆகிறது. மேலும் இப்பொழுது, அந்த மட்டுமே பகுதி வரிசை நாங்கள் மூலம் தீர்த்துக்கொள்ள வேண்டும். நாம் இப்போது குறைத்துவிட்டதால் 15 உறுப்புகள் 12. நாம் அறிவோம் 19 என்று வரிசை உள்ளது, அது உறுப்பு இடையே எங்கோ இருக்க வேண்டும் எண் 8 மற்றும் உறுப்பு எண் 10. 

எனவே நாம் மீண்டும் புதிய இடையில் கணக்கிட. 8 பிளஸ் 10 2 9 வகுக்க, 18 ஆகும். இந்த வழக்கில், பார்க்க, இலக்கு நடுத்தர உள்ளது. நாம் நாம் தேடும் என்பதை கண்டறிய. நாம் தடுத்து நிறுத்த முடியாது. நாம் வெற்றிகரமாக நிறைவு ஒரு பைனரி தேடல். எல்லாம் சரி. எனவே நாம் இந்த வழிமுறை தெரிகிறோம் இலக்கு என்றால் வேலை எங்காவது வரிசை உள்ளே. இந்த எப்படி வழிமுறை என்றால் என்ன இலக்கு வரிசை இல்லை? சரி, அது ஆரம்பிப்போம் மீண்டும், இந்த நேரத்தில், உறுப்பு பார்போம் பார்வை நாம் பார்க்க முடியும் 16, வரிசை எங்கும் இல்லை. 

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

எனவே படி முதல் என்ன? இடையில் கணக்கிட தற்போதைய வரிசைக்கு. இடையில் என்ன தற்போதைய வரிசைக்கு? சரி, அது சரி, 7 தான்? 2 வகுக்க 14 பிளஸ் 0 7. நாம் தேடும் என்ன 15 ஆகும்? இல்லை. அது மிகவும் நெருக்கமான, ஆனால் நாம் தேடும் என்று விட சற்று பெரியது ஒரு மதிப்பு. 

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

இப்போது, நாம் மீண்டும் இன்னும் ஒரு முறை செயல்படுத்த. புதிய இடையில் கணக்கிட. 8 பிளஸ் 14 2 11 ஆல் வகுக்க, 22 ஆகும். நாம் தேடும் என்ன 23 ஆகும்? துரதிர்ஷ்டவசமாக, எந்த. நாம் ஒரு மதிப்பு தேடும் என்று குறைவான 23 ஆகிறது. எனவே, இந்த விஷயத்தில், நாம் போகிறோம் இறுதியில் புள்ளி மாற்ற தான் இருக்க வேண்டும் தற்போதைய இடையில் இடது புறமாக. தற்போதைய இடையில் 11, மற்றும் எனவே நாம் புதிய இறுதியில் புள்ளி அமைக்க வேண்டும் நாங்கள் போய் அடுத்த முறை 10 இந்த செயல்முறை மூலம். 

மீண்டும், நாம் மீண்டும் செயல்முறை மூலம் சென்று. இடையில் கணக்கிட. 2 வகுக்க 8 பிளஸ் 10 9 ஆகும். நாம் தேடும் என்ன 19 ஆகும்? துரதிர்ஷ்டவசமாக, எந்த. நாம் இன்னும் தேடும் என்று குறைவான ஒரு எண். எனவே நாம் இறுதியில் புள்ளி இந்த நேரத்தில் மாற்ற வேண்டும் இடையில் இடது இருக்க வேண்டும். இடையில், தற்போது 9 எனவே இறுதியில் புள்ளி 8 இருக்கும். இப்போது, நாம் வெறும் தேடும் ஒரு உறுப்பு வரிசை. 

இந்த வரிசைக்கு இடையில் என்ன? சரி, அது, 8 மணிக்கு தொடங்குகிறது 8 மணிக்கு முடிவடைகிறது, இடையில் 8 ஆகிறது. என்று நாம் தேடும் என்ன? நாம் 17 தேடுகிறீர்கள்? இல்லை, நாங்கள் 16 தேடுகிறீர்கள். அது அணியின் உள்ளது என்றால், அது எங்கோ இருக்க வேண்டும் நாம் தற்போது எங்கே இடது புறமாக. எனவே நாங்கள் என்ன செய்ய போகிறோம்? சரி, நாம் இருக்கும் வரை இறுதி கட்டத்தில் அமைக்க வேண்டும் தற்போதைய இடையில் இடது புறமாக. எனவே நாம் 7 இறுதியில் புள்ளி மாற்ற வேண்டும். நீங்கள் என்ன தான் பார்க்கிறீர்கள் என்றாலும், இங்கு நடந்தது? இப்போது இங்கே பாருங்கள். 

தொடக்க இப்போது இறுதியில் விட அதிகமாக உள்ளது. இது, இரண்டு ஓரங்களிலும் எங்கள் அணி கடந்து, மற்றும் தொடக்க புள்ளியாக உள்ளது இப்போது இறுதி புள்ளி பின்னர். சரி, அந்த இல்லை வலது, எந்த உணர்வு? எனவே இப்போது, நாம் என்ன சொல்ல முடியும் நாம் உள்ளது அளவு 0 ஒரு துணை வரிசை உள்ளது. ஒருமுறை நாங்கள் விட்டிருக்கும் இந்த கட்டத்தில், நாம் இப்போது முடியும் அந்த உறுப்பு உத்தரவாதம் 16 வரிசை இல்லை, தொடக்க புள்ளியாக ஏனெனில் மற்றும் இறுதி கட்டத்தில் சென்றனர். அதனால் அங்கு இல்லை. இப்போது, இந்த சற்று கவனிக்க வேண்டும் என்று தொடக்க புள்ளியாக மற்றும் இறுதியில் விட வேறு அதே இருப்பது சுட்டிக்காட்டுகின்றனர். நாம் பார்க்கும் இருந்திருந்தால் 17, அது வேண்டும் வரிசை, மற்றும் தொடக்க புள்ளியாக இருந்து கடந்த ஹீரோக்களின் மற்றும் இறுதி கட்டத்தில் அந்த புள்ளிகள் கடந்து முன், நாம் அங்கு 17 கண்டிருப்பார்கள். நம்மைக் என்று கடந்து போது அது மட்டும் தான் உறுப்பு இல்லை என்று உத்தரவாதம் வரிசை உள்ளன. 

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

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

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

நான் டக் லாயிட் இருக்கிறேன். இந்த சிஎஸ் 50 ஆகும்.