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

[[കമ്പ്യൂട്ടർ ശാസ്ത്രം | കമ്പ്യൂട്ടർ ശാസ്ത്രത്തിൽ]] ഉൾപ്പെടുന്ന ഒരു അടിസ്ഥാന [[അൽഗോരിതം | അൽഗോരിതം]] ആണ് ബൈനറി തിരയൽ.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Binary search"}} [[ക്രമീകരണം | ക്രമീകരിയ്ക്കപ്പെട്ടിട്ടുള്ള]] ഒരു [[അറേ (കമ്പ്യൂട്ടർ ശാസ്ത്രം) | അറേയിൽ]] നിന്നും ഒരു പ്രത്യേക അംഗത്തെ കണ്ടുപിടിയ്ക്കാനുള്ള ഒരു അൽഗോരിതം ആണ് ഇത്. ഈ അറേയിലെ നടുക്കുള്ള അംഗവുമായി കണ്ടുപിടിയ്ക്കാനുള്ള അംഗത്തെ താരതമ്യം ചെയ്യുന്നു. അവ ഒന്നാണെങ്കിൽ സ്ഥാനം നടുക്കാണെന്ന് തീരുമാനിയ്ക്കാമല്ലോ. കണ്ടു പിടിയ്ക്കേണ്ട അംഗം നടുക്കല്ലെങ്കിൽ അത് രണ്ടു പകുതികളിൽ ഏതെങ്കിലും ഒന്നിൽ ആയിരിയ്ക്കും. അറേ ക്രമീകരിയ്ക്കപ്പെട്ടിട്ടുള്ളതായതുകൊണ്ട് ഏതെങ്കിലും ഒരു പകുതിയെ നമുക്ക് പൂർണമായും ഒഴിവാക്കാം. കണ്ടു പിടിയ്ക്കാനുള്ള അംഗം തീർച്ചയായും മറ്റേ പകുതിയിൽ എവിടെയെങ്കിലും ആയിരിയ്ക്കും. അടുത്ത ഘട്ടത്തിൽ മറ്റേ പകുതിയെ വീണ്ടും രണ്ടായി വിഭജിച്ചു തെരച്ചിൽ തുടരുന്നു. ഇങ്ങനെ ഇനി പകുതികൾ ആയി വിഭജിയ്ക്കാൻ പറ്റാത്ത ഒരു അവസ്ഥ എത്തുമ്പോൾ തീരുമാനിയ്ക്കാം തെരയുന്ന അംഗം അറേയിൽ ഇല്ല എന്ന്. ഓരോ തവണയും അപ്പോഴുള്ള അംഗങ്ങളുടെ പകുതി എണ്ണം തെരച്ചിലിൽ നിന്ന് ഒഴിവായി പോകുന്നതുകൊണ്ട് തെരച്ചിൽ വളരെ കാര്യക്ഷമം ആയിത്തീരുന്നു. അതിനാൽ ഈ അൽഗോരിതത്തിന്റെ [[കോംപ്ലക്സിറ്റി(കമ്പ്യൂട്ടർ ശാസ്ത്രം) | കോംപ്ലക്സിറ്റി]] [[ലോഗരിതമിക് കോംപ്ലക്സിറ്റി | ലോഗരിതമിക് ]] ആണെന്ന് പറയുന്നു.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Binary search"}}

 

== ഇതും കൂടി കാണുക ==