"ബൈനറി തിരയൽ" എന്ന താളിന്റെ പതിപ്പുകൾ തമ്മിലുള്ള വ്യത്യാസം
Content deleted Content added
No edit summary |
No edit summary |
||
വരി 1:
{{mergefrom|ബൈനറി സേർച്ച്}}
[[കമ്പ്യൂട്ടർ ശാസ്ത്രം |കമ്പ്യൂട്ടർ ശാസ്ത്രത്തിലെ]] ഒരു അടിസ്ഥാന [[അൽഗോരിതം]] ആണ് ബൈനറി തിരയൽ അഥവാ ദ്വയാംശത്തിരച്ചിൽ.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Binary search"}} [[ക്രമീകരണം |ക്രമീകരിയ്ക്കപ്പെട്ടിട്ടുള്ള]] ഒരു [[അടുക്ക് (ദത്തസങ്കേതം)|അടുക്കിൽ അഥവാ അറേയിൽ]] നിന്നും ഒരു പ്രത്യേക അംഗത്തെ കണ്ടുപിടിയ്ക്കാനുള്ള ഒരു അൽഗോരിതം ആണ് ഇത്. ഈ അടുക്കിലെ നടുക്കുള്ള അംഗത്തിന്റെ വിലയുമായി കണ്ടുപിടിയ്ക്കാനുള്ള അംഗത്തിന്റെ വിലയെ താരതമ്യം ചെയ്യുന്നു. അവ ഒന്നാണെങ്കിൽ സ്ഥാനം നടുക്കാണെന്ന് തീരുമാനിയ്ക്കാമല്ലോ. കണ്ടു പിടിയ്ക്കേണ്ട അംഗം നടുക്കല്ലെങ്കിൽ അത് രണ്ടു പകുതികളിൽ ഏതെങ്കിലും ഒന്നിൽ ആയിരിയ്ക്കും. അടുക്ക് ക്രമീകരിയ്ക്കപ്പെട്ടിട്ടുള്ളതായതുകൊണ്ട് ഏതെങ്കിലും ഒരു പകുതിയെ നമുക്ക് പൂർണമായും ഒഴിവാക്കാം. കണ്ടു പിടിയ്ക്കാനുള്ള അംഗം തീർച്ചയായും മറ്റേ പകുതിയിൽ എവിടെയെങ്കിലും ആയിരിയ്ക്കും. അടുത്ത ഘട്ടത്തിൽ മറ്റേ പകുതിയെ വീണ്ടും രണ്ടായി വിഭജിച്ചു തെരച്ചിൽ തുടരുന്നു. ഇങ്ങനെ ഇനി പകുതികൾ ആയി വിഭജിയ്ക്കാൻ പറ്റാത്ത ഒരു അവസ്ഥ എത്തുമ്പോൾ തീരുമാനിയ്ക്കാം തെരയുന്ന അംഗം അടുക്കിൽ ഇല്ല എന്ന്. ഓരോ തവണയും അപ്പോഴുള്ള അംഗങ്ങളുടെ പകുതി എണ്ണം തെരച്ചിലിൽ നിന്ന് ഒഴിവായി പോകുന്നതുകൊണ്ട് തെരച്ചിൽ വളരെ കാര്യക്ഷമം ആയിത്തീരുന്നു. അതിനാൽ ഈ അൽഗോരിതത്തിന്റെ [[കോംപ്ലക്സിറ്റി(കമ്പ്യൂട്ടർ ശാസ്ത്രം) |സമയ സങ്കീർണ്ണത]] (Time complexity)[[ലോഗരിതമിക് കോംപ്ലക്സിറ്റി | ലോഗരിതമിക് ]]<nowiki/>ആണെന്ന് പറയുന്നു.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Binary search"}}
<math>n</math> അംഗങ്ങളുള്ള ഒരടുക്കിൽ ഈ അൽഗോരിതം <math>O(\log n)</math> താരതമ്യങ്ങൾ നടത്തുന്നു. അതിനാൽ അൽഗോരിതത്തിന്റെ സമയസങ്കീർണ്ണത <math>O(\log n)</math> ആണ്. ഉപയോഗിയ്ക്കുന്ന സ്ഥലത്തിന്റെ വലിപ്പം ഒരു സ്ഥിരസംഖ്യയാണ്. അതുകൊണ്ട് അതിന്റെ സ്ഥലസങ്കീർണ്ണത (Space complexity) <math>O(1)</math> ആണ്<ref name="avgperf">{{cite journal|last1=Flores|first1=Ivan|last2=Madpis|first2=George|title=Average binary search length for dense ordered lists|journal=[[Communications of the ACM]]|date=1971|volume=14|issue=9|doi=10.1145/362663.362752|pages=602–603}}</ref>.
| |||