ബൈനറി തിരയൽ - ശ്രേണിയിലെ ഘടകം കണ്ടെത്താൻ എളുപ്പമാർഗമാണ്

പലപ്പോഴും, പ്രോഗ്രാമർമാർ, പോലും തുടക്കക്കാർ, ഒരു പ്രത്യേക നമ്പർ കണ്ടെത്താൻ വേണം ഏത് സംഖ്യകളുടെ ഒരു കൂട്ടം, ഇല്ല വസ്തുത നേരിടുന്ന. ഈ ശേഖരം ഒരു അറേ ആണ് .സി. എന്നാൽ അതിൽ ഇനങ്ങൾ കണ്ടെത്താൻ, വഴികൾ പതിനായിരം ഉണ്ട്. എന്നാൽ അവരിൽ ഏറ്റവും ലളിതമായ വലതുഭാഗത്ത് ഒരു ബൈനറി തിരയൽ പരിഗണിക്കാം. ഈ രീതി എന്താണ് ആണ്? എത്ര ബൈനറി തിരയൽ നടപ്പാക്കാൻ? പാസ്കൽ അത്തരം ഒരു പ്രോഗ്രാമിന്റെ സംഘടന വേണ്ടി ഏറ്റവും എളുപ്പ പരിസ്ഥിതി, ഞങ്ങൾക്ക് പഠിക്കാൻ ഉപയോഗിക്കും.

ആദ്യം, വിശകലനം ഈ രീതി? എന്താണ്, അത് നമുക്ക് മനസ്സിലാക്കാൻ കഴിയും, വിഷയം പഠിക്കാൻ പോയിന്റ് എന്താണ്. അതിനാൽ, ചില കണ്ടെത്താൻ മാറ്റേണ്ട കുറഞ്ഞത് 100000000 ഘടകങ്ങൾ, ഒരു മാനം ഒരു അറേ ഉണ്ടാകട്ടെ. തീർച്ചയായും, ഈ പ്രശ്നം എളുപ്പത്തിൽ ഒരു ലളിതമായ ലീനിയർ തിരയൽ, നാം സൈക്കിൾ ഉപയോഗിക്കുന്ന പരിഹരിക്കാൻ കഴിയും അറേ എല്ലാവർക്കും കൂട്ടത്തിൽ ആവശ്യമായ ഘടകം താരതമ്യം ചെയ്യും. പ്രശ്നം ഈ ആശയം നടപ്പാക്കാൻ കൂടുതൽ സമയം എടുക്കും എന്നതാണ്. നിരവധി ചികിത്സകൾ, പ്രധാന പാഠം മൂന്നു ഒരു ലളിതമായ പാസ്കൽ പ്രോഗ്രാം, നിങ്ങൾ അത് ശ്രദ്ധിച്ചില്ലെന്നു, പക്ഷേ ഞങ്ങൾ ശാഖകൾ ഒരു വലിയ എണ്ണം നല്ല പ്രവർത്തനം ഒരു കൂടുതലോ കുറവോ വലിയ പദ്ധതികൾക്ക് വരുമ്പോൾ, പ്രോഗ്രാം വളരെ നേരം ലഭ്യമാക്കുവാനുള്ള തയ്യാറാകും. പ്രത്യേകിച്ച് കമ്പ്യൂട്ടർ ഒരു ദുർബലമായ പ്രകടനം എങ്കിൽ. അതുകൊണ്ടു, കുറഞ്ഞത് രണ്ടുതവണ സമയ കുറയ്ക്കുന്നു ഒരു ബൈനറി സെർച്ച്, ഇല്ല.

അതുകൊണ്ട്, ഈ രീതി തൊഴിലാളി തത്ത്വം എന്താണ്? ഉടനെ അത് ബൈനറി തിരയൽ പ്രവർത്തിക്കുന്നത് ഏതെങ്കിലും അണിനിരന്നു, എന്നാൽ നമ്പറുകൾ മാത്രം ഒരു വരിയോ സെറ്റിൽ അല്ല എന്ന് വേണം. ഓരോ ഘട്ടത്തിലും അറേ മധ്യത്തിൽ ഘടകം (ഘടകത്തിന്റെ എണ്ണം അർത്ഥം) എടുത്ത. ആവശ്യമായ എങ്കിൽ എണ്ണം വലിയവൻ ശരാശരി, മറ്റേ എല്ലാവരും ആ ശരാശരി സെൽ കുറവാണ്, നിരസിക്കപ്പെടും കഴിയും അവിടെ നോക്കി അല്ല. അതുപോലെ, ശരാശരിയേക്കാൾ കുറവാണ് എങ്കിൽ - ആ നമ്പറുകൾ വലതുവശത്ത് ഇടയിൽ, നിങ്ങൾ പാടില്ല. അപ്പോൾ ആദ്യത്തെ ഘടകം മുഴുവൻ അറേ, കഴിഞ്ഞ കഴിഞ്ഞ ഇഷ്ടം മധ്യത്തിൽ ഘടകം അവിടെ ഒരു പുതിയ തിരയൽ മേഖല, തിരഞ്ഞെടുക്കുക. പുതിയ വയലിലെ ശരാശരി എണ്ണം എല്ലാ വിഭാഗത്തിൽപ്പെട്ട കാൽ, അതായത്, (കഴിഞ്ഞ ഘടകം + മുഴുവൻ അറേ മധ്യത്തിൽ ഘടകം) / 2 ആയിരിക്കും. വീണ്ടും, അതേ പ്രവർത്തനം നടപ്പാകും - ശ്രേണിയുടെ ശരാശരി എണ്ണം ഒരു താരതമ്യം. ലക്ഷ്യം മൂല്യം ശരാശരി താഴെയാണെങ്കിൽ, ഞങ്ങൾ വലത് വശത്ത് നിഷേധിച്ചു, കൂടാതെ ഇപ്പോൾ ഈ മധ്യ ഘടകം ആവശ്യമുള്ള വിചാരിക്കുന്നില്ല, ചെയ്യണം.

തീർച്ചയായും, ബൈനറി തിരയൽ എഴുതാൻ എങ്ങനെ ഒരു ഉദാഹരണം നോക്കാം നല്ലത്. പാസ്കൽ ഇവിടെ ആരെയും അനുയോജ്യമായതാണ് - പതിപ്പിൽ പ്രധാനപ്പെട്ട അല്ല. ഒരു ലളിതമായ പ്രോഗ്രാം എഴുതാം.

അതു പേര് "മഷിവ്" കീഴിൽ H 1 ഒരു അറേ, സെർച്ച് ന്റെകീഴ്അതിരു്, "നിജ്" വിളിച്ചു സൂചിപ്പിക്കുന്ന ഒരു വേരിയബിൾ, പരിധി, "വെര്ഹ്" വിളിച്ചു ശരാശരി തിരയൽ പദം ആണ് - "സ്രെദ്ന്"; ആവശ്യമായ എണ്ണം - "ISK".

അതിനാൽ, നമ്മൾ സംഖൃകളോടൊപ്പം എന്ന മലയിലും പരിധി നിയോഗിക്കുകയോ:

നിജ്: = 1;
വെര്ഹ്: = H + 1;

അപ്പോൾ സൈക്കിൾ സംഘടിപ്പിക്കാൻ "താഴെ പരിധി കുറവാണ് വരെ":

നിജ് <വെര്ഹ് സമയത്ത് - 1 ചെയ്യാൻ
തുടങ്ങുക

ഓരോ ഘട്ടത്തിലും, ഞങ്ങൾ വിഭാഗത്തിൽ 2 പങ്കിടും:

സ്രെദ്ന്: = (നിജ് + വെര്ഹ്) കളരി 2; {ബാക്കി ഇല്ലാതെ കാരണം വിഭജനം, ഫംഗ്ഷൻ DIV ഉപയോഗിക്കുക}

അവലോകനം ഓരോ സമയം. കാരണം ഇടത്തരം ആവശ്യമുള്ള പക്ഷം ഇനം ഇതിനകം കണ്ടെത്തി, സൈക്കിൾ തടസ്സപ്പെടും:

.ജനകീയനായ സ്രെദ്ന് = ISK പിന്നീട് പൊട്ടി;

ആവശ്യമുള്ള അധികം അറേ കൂടുതൽ മധ്യത്തിൽ ഘടകം എങ്കിൽ,, ഇടതുവശത്തെ ഉപേക്ഷിക്കുക അതായത്, ശരാശരി ന്റെമേലതിരു് ഘടകം നിയമിക്കും:

മഷിവ് [സ്രെദ്ന്]> ISK എങ്കിൽ പിന്നെ വെര്ഹ്: = സ്രെദ്ന്;

എന്നാൽ മറിച്ച്, അത് താഴത്തെ അതിർത്തി ചെയ്യുന്നു:

മറ്റാരെങ്കിലും നിജ്: = സ്രെദ്ന്;
അവസാനം;

ആ പ്രോഗ്രാമിൽ ആയിരിക്കും അത്രയേയുള്ളൂ.

ഞങ്ങളെ അത് പ്രായോഗികമായി ബൈനറി രീതി നോക്കി എങ്ങനെ പരിചിന്തിക്കാം. ഈ അറേ ചിന്തിക്കുക: 1, 3, 5, 7, 10, 12, 18 അതു നമ്പർ 12 അന്വേഷിക്കും.

മൊത്തം ഞങ്ങൾ 7 ഘടകങ്ങൾ, അങ്ങനെ നാലാം ഇടത്തരം ചെയ്യും, മൂല്യം 7.

12 ലധികം, 7, 1.3 5 ഘടകങ്ങൾ, ഞങ്ങൾ നിരസിക്കുക. അപ്പോൾ നാം നമ്പർ 4, 4/2 യാതൊരു ശേഷിപ്പും അങ്ങനെ 2. ആണ്, ഒരു പുതിയ ഘടകം 10 ശരാശരി ആയിരിക്കും ലഭിച്ചു.

12 10 വലിയവൻ, ഞങ്ങൾ 7. തുടരുന്നു 10, 12 18 ഉപേക്ഷിക്കുക.

ഇവിടെ, മധ്യ ഘടകം ഇതിനകം 12, അത് ആവശ്യമായ എണ്ണം ആണ്. ഈ ചുമതല പൂർത്തിയായി - നമ്പർ 12 കണ്ടെത്തി.