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

ഇടത്തുനിന്ന് വലത്തോട്ട് നീങ്ങുമ്പോൾ സംഖ്യകൾ വലുതായി വരുന്ന ഒരു അടുക്കിൽ ഒരു നിശ്ചിതസംഖ്യ <math>x </math> തിരയേണമെങ്കിൽ, ബൈനറി തിരയൽ പ്രകാരം അടുക്കിന്റെ നടുക്കുള്ള സംഖ്യ <math>mid</math>ഉമായി <math>x</math>നെ താരതമ്യം ചെയ്യുക. <math>x = mid</math> ആണെങ്കിൽ (ചോദ്യത്തിന്റെ ഉത്തരം ലഭിച്ച കാരണം) തിരച്ചിൽ അവിടെ തീരുന്നു. <math>x < mid</math> ആണെങ്കിൽ അടുക്കിന്റെ ആദ്യപകുതിയിലേ <math>x</math> ഉണ്ടാവുകയുള്ളൂ. അതിനാൽ <math>x</math>നു വേണ്ടി അടുക്കിന്റെ ആദ്യപകുതിയിൽ ബൈനറി തിരയൽ നടത്തുക. അല്ലെങ്കിൽ അടുക്കിന്റെ രണ്ടാം പകുതിയിൽ <math>x</math>നു വേണ്ടി ബൈനറി തിരയൽ നടത്തുക. ഇങ്ങനെ ഇനി പകുതികൾ ആയി വിഭജിയ്ക്കാൻ പറ്റാത്ത ഒരു അവസ്ഥ എത്തിയിട്ടും അടുക്കിൽ <math>x</math> എന്ന സംഖ്യ കൺറ്റുകിട്ടിയില്ല എങ്കിൽ <math>x</math> അടുക്കിൽ ഇല്ല എന്ന് തീരുമാനിക്കാം. ഓരോ തവണയും അപ്പോഴുള്ള അംഗങ്ങളുടെ പകുതി എണ്ണം തെരച്ചിലിൽ നിന്ന് ഒഴിവായി പോകുന്നതുകൊണ്ട് തെരച്ചിൽ വളരെ കാര്യക്ഷമം ആണ്. തിരച്ചിലിന്റെ [[സമയസങ്കീർണ്ണതസമയ സങ്കീർണ്ണത(കമ്പ്യൂട്ടർ ശാസ്ത്രം) |സമയ സങ്കീർണ്ണത]] (Time complexity)[[ലോഗരിതമിക് കോംപ്ലക്സിറ്റി | ലോഗരിതമിക്]] ആണെന്ന് പറയുന്നു.{{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>.

ഈ അൽഗോരിതത്തിന്റെ കാര്യക്ഷമത പരിശോധിയ്ക്കാനായി ഇതിനെ ഒരു [[ട്രീ(കമ്പ്യൂട്ടർ ശാസ്ത്രം) | ട്രീയോട്]] ഉപമിയ്ക്കാം. മധ്യത്തിൽ ഉള്ള വില ആയിരിയ്ക്കും ട്രീയുടെ [[മൂലം(കമ്പ്യൂട്ടർ ശാസ്ത്രം) | മൂലം]]. ഈ വിലയേക്കാൾ കുറഞ്ഞ അംഗങ്ങൾ ഉള്ള അടുക്കിന്റെ പകുതി ഈ ട്രീയുടെ ഇടത്തെ സബ്-ട്രീയും മറ്റേ പകുതി വലത്തേ സബ്-ട്രീയും ആയി കണക്കാക്കാം. തുടർന്ന് അടുത്ത നിലയിൽ ഉള്ള സബ്-ട്രീകളിലേയ്ക്ക് പോകുമ്പോൾ ഓരോ പകുതിയിലെയും മദ്ധ്യ വില ആ സബ്-ട്രീയുടെ മൂലം ആയിരിയ്ക്കും. ഇങ്ങനെ കിട്ടുന്ന ഒരു ട്രീയെ [[ബൈനറി സെർച്ച് ട്രീ]] എന്ന് വിളിയ്ക്കുന്നു. ഉദാഹരണത്തിന് മുകളിൽ കാണിച്ചിട്ടുള്ള അടുക്കിനെ വലതുവശത്തു കാണുന്ന ഒരു ബൈനറി സെർച്ച് ട്രീ ആയി ചിത്രീകരിയ്ക്കാം. ഇനി നമ്മുടെ തിരയൽ എന്ന പ്രവൃത്തിയെ ട്രീയുടെ മൂലം മുതൽ ഉള്ള ഒരു നടത്തം ആയി കാണാം. ആദ്യം മൂലത്തിലുള്ള വിലയുമായി നമ്മുടെ തിരയുന്ന വിലയെ താരതമ്യപ്പെടുത്തുന്നു. അവ തമ്മിൽ തുല്യമാണെങ്കിൽ നമ്മുടെ തിരയൽ ഫലപ്രദമായി, ഇനി തിരയൽ അവസാനിപ്പിയ്ക്കാം. തുല്യമല്ലെങ്കിൽ പിന്നെ നമ്മൾ തിരയുന്ന വില മൂലത്തിലുള്ള വിലയേക്കാൾ കൂടുതൽ ആണോ എന്ന് നോക്കുക, അങ്ങനെ ആണെങ്കിൽ വലത്തേ സബ്-ട്രീയിലേക്കു പോകുക. അല്ലെങ്കിൽ ഇടത്തെ സബ്-ട്രീയിലേയ്ക്കും. ഇങ്ങനെ നോക്കുമ്പോൾ ഏതൊരു വിലയെ കണ്ടു പിടിയ്ക്കാനും ഏറ്റവും കൂടുതൽ നമ്മൾ ട്രീയുടെ അഗ്രം വരെ മാത്രമേ പോകേണ്ടതുള്ളൂ. അതായത് നമ്മൾ നടത്തേണ്ട പരമാവധി താരതമ്യങ്ങളുടെ എണ്ണം എന്ന് പറയുന്നത് ഈ ട്രീയുടെ ഉയരം എത്രയാണോ അതാണ്. <math display="inline">n</math> അംഗങ്ങളുള്ള ഒരു ബൈനറി സെർച്ച് ട്രീയുടെ ഉയരം <math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math> ആണ്.{{sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}{{sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}. അതുകൊണ്ട് <math display="inline">\log_2</math> ആണ് ബൈനറി തിരയലിന്റെ സമയസങ്കീർണ്ണതസമയ സങ്കീർണ്ണത എന്നു പറയാം.

* [[സമയസങ്കീർണ്ണതസമയ സങ്കീർണ്ണത(കമ്പ്യൂട്ടർ ശാസ്ത്രം) |സമയസങ്കീർണ്ണതസമയ സങ്കീർണ്ണത]]