ബൈനറി തിരയൽ

ഇംഗ്ലീഷ് വിലാസം

https://ml.wikipedia.org/wiki/Binary_Search

കമ്പ്യൂട്ടർ ശാസ്ത്രത്തിലെ ഒരു അടിസ്ഥാന അൽഗോരിതം ആണ് ദ്വയാംശത്തിരച്ചിൽ അഥവാ ബൈനറി തിരയൽ (Binary search) .^[1] കൂടുംക്രമത്തിലോ കുറയും ക്രമത്തിലോ സംഖ്യകളടുക്കി വച്ച ഒരു അടുക്കിൽ (അറേയിൽ) ഒരു നിശ്ചിതസംഖ്യ തിരയാനുള്ള ഒരു അൽഗോരിതം ആണ് ഇത്. ഇംഗ്ലീഷിൽ ഇതിനെ ബൈനറി സെർച്ച് (Binary Search) എന്ന് വിളിക്കുന്നു.

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

${\displaystyle n}$ അംഗങ്ങളുള്ള ഒരടുക്കിൽ ഈ അൽഗോരിതം ${\displaystyle O(\log n)}$ താരതമ്യങ്ങൾ നടത്തുന്നു. അതിനാൽ അൽഗോരിതത്തിന്റെ സമയ സങ്കീർണ്ണത ${\displaystyle O(\log n)}$ ആണ്. ഉപയോഗിയ്ക്കുന്ന സ്ഥലത്തിന്റെ വലിപ്പം ഒരു സ്ഥിരസംഖ്യയാണ്. അതുകൊണ്ട് അതിന്റെ സ്ഥല സങ്കീർണ്ണത (Space complexity) ${\displaystyle O(1)}$ ആണ്^[2].

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

ഈ അൽഗോരിതത്തിന്റെ പടികൾ താഴെ കൊടുത്തിരിയിക്കുന്നു.

കൂടുംക്രമത്തിൽ അടുക്കിയിരിക്കുന്ന ${\displaystyle n}$ അംഗങ്ങളുള്ള ${\displaystyle A}$ എന്ന ഒരടുക്ക് സങ്കല്പിക്കുക. ${\displaystyle A}$യിലെ അംഗങ്ങൾ ${\displaystyle A_{0},A_{1},\dots A_{n-1}}$ എന്നിവ ആണെന്ന് കരുതുക. ഇവ കൂടുംക്രമത്തിൽ ആയതുകൊണ്ട് നിശ്ചയമായും ${\displaystyle A_{0}\leq A_{1}\leq \dots \leq A_{n-1}}$ ആയിരിയ്ക്കും.

പ്രശ്നവാചകം: ${\displaystyle t}$ എന്ന സംഖ്യ ${\displaystyle A}$യിലെ അംഗമാണോ എന്ന് നിർണ്ണയിക്കുക.

താഴെ കൊടുത്തിരിയ്ക്കുന്ന നിർദ്ദേശങ്ങൾ പടിപടിയായി പിന്തുടർന്നാൽ ${\displaystyle t}$ എന്ന സംഖ്യ ${\displaystyle A}$യിലെ അംഗമാണോ എന്നും ആണെങ്കിൽ അതിന്റെ സ്ഥാനാങ്കം (Index) എത്രയെന്നും കണ്ടുപിടിക്കാനാവും.^[3]

1. ${\displaystyle L}$നു 0 എന്നും ${\displaystyle R}$നു ${\displaystyle n-1}$ എന്നും വില കൊടുക്കുക.
2. ${\displaystyle L>R}$ ആണെങ്കിൽ നമ്മുടെ തിരച്ചിൽ ഫലപ്രദമായില്ല. തിരച്ചിൽ നിറുത്തുക.
3. ${\displaystyle M}$നു (നടുവിലെ അംഗത്തിന്റെ സ്ഥാനാങ്കം) ${\displaystyle \left\lfloor {\frac {L+R}{2}}\right\rfloor }$ എന്ന വില കൊടുക്കുക. (കുറിപ്പ്: ${\displaystyle M}$ എന്ന പ്രതീകം, ഇപ്പോൾ പ്രസക്തമായ അടുക്കിലെ നടുവിലത്തെ അംഗത്തിന്റെ സ്ഥാനാങ്കത്തെ കുറിക്കുന്നു. ${\displaystyle \lfloor x\rfloor }$ എന്ന പ്രതീകം, ${\displaystyle x}$ നെക്കാൾ ചെറിയ ഏറ്റവും വലിയ എണ്ണൽസംഖ്യയെ കുറിക്കുന്നു.)
4. ${\displaystyle A_{M}<t}$ ആണെങ്കിൽ, ${\displaystyle L}$ന് ${\displaystyle M+1}$ എന്ന വില കൊടുത്തു സ്റ്റെപ് 2 ലേയ്ക്ക് പോകുക.
5. ${\displaystyle A_{M}>t}$ ആണെങ്കിൽ, ${\displaystyle R}$ന് ${\displaystyle M-1}$ എന്ന വില കൊടുത്തു സ്റ്റെപ് 2 ലേയ്ക്ക് പോകുക.
6. ${\displaystyle A_{M}=t}$ ആണെങ്കിൽ, തിരയൽ ഫലപ്രദമായി. ${\displaystyle t}$യുടെ സ്ഥാനാങ്കമായി ${\displaystyle M}$ തിരിച്ചു കൊടുത്ത് നിറുത്തുക.

ബൈനറി തിരയലിന്റെ ഒരു ഉദാഹരണം താഴെ കൊടുത്തിരിയ്ക്കുന്നു.

ഈ അൽഗോരിതത്തിന്റെ കാര്യക്ഷമത പരിശോധിയ്ക്കാനായി ഇതിനെ ഒരു ട്രീയോട് ഉപമിയ്ക്കാം. മധ്യത്തിൽ ഉള്ള വില ആയിരിയ്ക്കും ട്രീയുടെ മൂലം. ഈ വിലയേക്കാൾ കുറഞ്ഞ അംഗങ്ങൾ ഉള്ള അടുക്കിന്റെ പകുതി ഈ ട്രീയുടെ ഇടത്തെ സബ്-ട്രീയും മറ്റേ പകുതി വലത്തേ സബ്-ട്രീയും ആയി കണക്കാക്കാം. തുടർന്ന് അടുത്ത നിലയിൽ ഉള്ള സബ്-ട്രീകളിലേയ്ക്ക് പോകുമ്പോൾ ഓരോ പകുതിയിലെയും മദ്ധ്യ വില ആ സബ്-ട്രീയുടെ മൂലം ആയിരിയ്ക്കും. ഇങ്ങനെ കിട്ടുന്ന ഒരു ട്രീയെ ബൈനറി സെർച്ച് ട്രീ എന്ന് വിളിയ്ക്കുന്നു. ഉദാഹരണത്തിന് മുകളിൽ കാണിച്ചിട്ടുള്ള അടുക്കിനെ വലതുവശത്തു കാണുന്ന ഒരു ബൈനറി സെർച്ച് ട്രീ ആയി ചിത്രീകരിയ്ക്കാം. ഇനി നമ്മുടെ തിരയൽ എന്ന പ്രവൃത്തിയെ ട്രീയുടെ മൂലം മുതൽ ഉള്ള ഒരു നടത്തം ആയി കാണാം. ആദ്യം മൂലത്തിലുള്ള വിലയുമായി നമ്മുടെ തിരയുന്ന വിലയെ താരതമ്യപ്പെടുത്തുന്നു. അവ തമ്മിൽ തുല്യമാണെങ്കിൽ നമ്മുടെ തിരയൽ ഫലപ്രദമായി, ഇനി തിരയൽ അവസാനിപ്പിയ്ക്കാം. തുല്യമല്ലെങ്കിൽ പിന്നെ നമ്മൾ തിരയുന്ന വില മൂലത്തിലുള്ള വിലയേക്കാൾ കൂടുതൽ ആണോ എന്ന് നോക്കുക, അങ്ങനെ ആണെങ്കിൽ വലത്തേ സബ്-ട്രീയിലേക്കു പോകുക. അല്ലെങ്കിൽ ഇടത്തെ സബ്-ട്രീയിലേയ്ക്കും. ഇങ്ങനെ നോക്കുമ്പോൾ ഏതൊരു വിലയെ കണ്ടു പിടിയ്ക്കാനും ഏറ്റവും കൂടുതൽ നമ്മൾ ട്രീയുടെ അഗ്രം വരെ മാത്രമേ പോകേണ്ടതുള്ളൂ. അതായത് നമ്മൾ നടത്തേണ്ട പരമാവധി താരതമ്യങ്ങളുടെ എണ്ണം എന്ന് പറയുന്നത് ഈ ട്രീയുടെ ഉയരം എത്രയാണോ അതാണ്. ${\textstyle n}$ അംഗങ്ങളുള്ള ഒരു ബൈനറി സെർച്ച് ട്രീയുടെ ഉയരം ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ ആണ്.^[4][4]. അതുകൊണ്ട് ${\textstyle \log _{2}}$ ആണ് ബൈനറി തിരയലിന്റെ സമയ സങ്കീർണ്ണത എന്നു പറയാം.

• തിരയൽ
• ക്രമീകരണം
• സമയ സങ്കീർണ്ണത
• ട്രീ
• ബൈനറി ട്രീ
• അടുക്ക്

1. ↑ ^{1.0 1.1} Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Binary search". sfn error: no target: CITEREFKnuth1998 (help)
2. ↑ Flores, Ivan; Madpis, George (1971). "Average binary search length for dense ordered lists". Communications of the ACM. 14 (9): 602–603. doi:10.1145/362663.362752.
3. ↑ Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Algorithm B". sfn error: no target: CITEREFKnuth1998 (help)
4. ↑ ^{4.0 4.1} Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search". sfn error: no target: CITEREFKnuth1998 (help)