വിക്കിപീഡിയ

"ബൈനറി തിരയൽ" എന്ന താളിന്റെ പതിപ്പുകൾ തമ്മിലുള്ള വ്യത്യാസം

നാൾപ്പതിപ്പുകൾ കാണുക
← മുൻപത്തെ വ്യത്യാസംഅടുത്ത വ്യത്യാസം →
Content deleted Content added
വ്യത്യാസം കാണൽവിക്കിഎഴുത്ത്
No edit summary
ഗണിതാക്ഷരങ്ങൾ ലാറ്റെക്ക് രീതിയിലാക്കി. അറേ എന്ന വാക്കിനു പകരം അടുക്ക് എന്ന വാക്കുപയോഗിച്ചു. സ്റ്റെപ്പിനു പകരം പടി എന്നാക്കി.
വരി 9:
ഈ അൽഗോരിതത്തിന്റെ പടികൾ താഴെ കൊടുത്തിരിയിക്കുന്നു.
 
കൂടുംക്രമത്തിൽ അടുക്കിയിരിക്കുന്ന <math>n</math> അംഗങ്ങളുള്ള <math>A</math> എന്ന ഒരടുക്ക് സങ്കല്പിക്കുക. <math>A</math>യിലെ അംഗങ്ങൾ <math>A_0, A_1, \dots A_{n-1}</math> എന്നിവ ആണെന്ന് കരുതുക. ഇവ കൂടുംക്രമത്തിൽ ആയതുകൊണ്ട് നിശ്ചയമായും <math>A_0 \le A_1 \le \dots \le A_{n-1}</math> ആയിരിയ്ക്കും.
A എന്ന ക്രമീകരിയ്ക്കപ്പെട്ട ഒരു അടുക്ക് ഉണ്ടെന്നും അതിലെ അംഗങ്ങളുടെ എണ്ണം n ആണെന്നും കരുതുക. ഇതിലെ അംഗങ്ങൾ ''A''<sub>0</sub>, ''A''<sub>1</sub>, ..., ''A''<sub>''n''−1</sub> എന്നിവ ആണെന്ന് കരുതുക. ഇവ ക്രമീകരിയ്ക്കപ്പെട്ടിട്ടുള്ളത് ആയതുകൊണ്ട് നിശ്ചയമായും ''A''<sub>0</sub> ≤ ''A''<sub>1</sub> ≤ ... ≤ ''A''<sub>''n''−1</sub> ആയിരിയ്ക്കും. നമ്മൾ തിരയുന്ന വില T ആണെന്ന് വിചാരിയ്ക്കുക. താഴെ കൊടുത്തിരിയ്ക്കുന്ന സ്റ്റെപ്പുകൾ A യിലെ T യുടെ സ്ഥാനം (ഇൻഡക്സ്) കണ്ടു പിടിയ്ക്കും.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Algorithm B"}}
 
പ്രശ്നവാചകം: <math>t</math> എന്ന സംഖ്യ <math>A</math>യിലെ അംഗമാണോ എന്ന് നിർണ്ണയിക്കുക.
# ''L'' നു 0 എന്നും ''R'' നു ''n'' &minus; 1 എന്നും വില കൊടുക്കുക.▼
 
# ''L'' > ''R'' ആണെങ്കിൽ നമ്മുടെ തിരച്ചിൽ ഫലപ്രദമായില്ല. തിരച്ചിൽ നിറുത്തുക.▼
താഴെ കൊടുത്തിരിയ്ക്കുന്ന നിർദ്ദേശങ്ങൾ പടിപടിയായി പിന്തുടർന്നാൽ <math>t</math> എന്ന സംഖ്യ <math>A</math>യിലെ അംഗമാണോ എന്നും ആണെങ്കിൽ അതിന്റെ [[അടുക്ക് (ദത്തസങ്കേതം)|സ്ഥാനാങ്കം]] (Index) എത്രയെന്നും കണ്ടുപിടിക്കാനാവും.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Algorithm B"}}
# ''m'' (നടുവിലെ അംഗത്തിന്റെ സ്ഥാനം) നു (''L'' + ''R'') / 2 ന്റെ [[Floor and ceiling functions|floor]] (ഇതിനു മുൻപുള്ള ഏറ്റവും വലിയ എണ്ണൽസംഖ്യ) വില കൊടുക്കുക.
 
# ''A''<sub>''m''</sub> < ''T'' ആണെങ്കിൽ, ''L'' ന് ''m'' + 1 എന്ന വില കൊടുത്തു സ്റ്റെപ് 2 ലേയ്ക്ക് പോകുക.▼
▲# ''<math>L</math>'' നു 0 എന്നും ''<math>R</math>'' നു ''<math>n'' &minus;- 1</math> എന്നും വില കൊടുക്കുക.
# ''A''<sub>''m''</sub> > ''T'' ആണെങ്കിൽ, ''R'' ന് ''m'' &minus; 1 എന്ന വില കൊടുത്തു സ്റ്റെപ് 2 ലേയ്ക്ക് പോകുക.▼
▲# ''<math>L'' > ''R''</math> ആണെങ്കിൽ നമ്മുടെ തിരച്ചിൽ ഫലപ്രദമായില്ല. '''തിരച്ചിൽ നിറുത്തുക'''.
# ''A''<sub>''m''</sub> = ''T'' ആണെങ്കിൽ, തിരയൽ ഫലപ്രദമായി അവസാനിച്ചിരിയ്ക്കുന്നു. ''m'' ''T'' യുടെ സ്ഥാനം ആയി തിരിച്ചു കൊടുക്കുക.
# ''<math>M</math>''നു (നടുവിലെ അംഗത്തിന്റെ സ്ഥാനാങ്കം) <math>\left \lfloor \frac{L+R}{2} \right \rfloor</math> എന്ന വില കൊടുക്കുക. ('''കുറിപ്പ്''': <math>M</math> എന്ന പ്രതീകം, ഇപ്പോൾ പ്രസക്തമായ അടുക്കിലെ നടുവിലത്തെ അംഗത്തിന്റെ സ്ഥാനാങ്കത്തെ കുറിക്കുന്നു. <math>\lfloor x \rfloor</math> എന്ന പ്രതീകം, <math>x</math> നെക്കാൾ ചെറിയ ഏറ്റവും വലിയ എണ്ണൽസംഖ്യയെ കുറിക്കുന്നു.)
▲# ''A''<submath>''m''A_M < t</submath> < ''T'' ആണെങ്കിൽ, ''<math>L</math>'' ന് ''m'' <math>M+ 1</math> എന്ന വില കൊടുത്തു സ്റ്റെപ് 2 ലേയ്ക്ക് പോകുക.
▲# ''A''<submath>A_M >''m'' t</submath> > ''T'' ആണെങ്കിൽ, ''<math>R</math>'' ന് ''m''<math>M &minus;- 1</math> എന്ന വില കൊടുത്തു സ്റ്റെപ് 2 ലേയ്ക്ക് പോകുക.
# <math>A_M = t</math> ആണെങ്കിൽ, തിരയൽ ഫലപ്രദമായി. <math>t</math>യുടെ സ്ഥാനാങ്കമായി <math>M</math> '''തിരിച്ചു കൊടുത്ത് നിറുത്തുക.'''
 
==ഉദാഹരണം==
"https://ml.wikipedia.org/wiki/ബൈനറി_തിരയൽ" എന്ന താളിൽനിന്ന് ശേഖരിച്ചത്