[[കമ്പ്യൂട്ടർ ശാസ്ത്രം |കമ്പ്യൂട്ടർ ശാസ്ത്രത്തിൽശാസ്ത്രത്തിലെ]] ഉൾപ്പെടുന്ന ഒരു അടിസ്ഥാന [[അൽഗോരിതം | അൽഗോരിതം]] ആണ് ബൈനറി തിരയൽ.{{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|{{italicsഅൽഗോരിതം correction|''<math>O''}}(\log ''n'')}}</math> താരതമ്യങ്ങൾ നടത്തുന്നു. അതിനാൽ അൽഗോരിതത്തിന്റെ സമയസങ്കീർണ്ണത <math>O(\log n)</math> ആണ്. ഉപയോഗിയ്ക്കുന്ന സ്ഥലംസ്ഥലത്തിന്റെ ആകട്ടെവലിപ്പം ഒരിക്കലുംഒരു മാറുന്നുമില്ലസ്ഥിരസംഖ്യയാണ്. അതുകൊണ്ട് അതിന്റെ സ്പേസ് കോംപ്ലക്സിറ്റിസ്ഥലസങ്കീർണ്ണത ({{math|{{italicsSpace correction|''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>.
== അൽഗൊരിതം ==
ക്രമീകരിയ്ക്കപ്പെട്ടിട്ടുള്ള ഒരു അറേയിൽ[[അടുക്ക് ആണ്(ദത്തസങ്കേതം)|അടുക്കിൽ]] മാത്രമേ ഈ അൽഗോരിതം ഓടിയ്ക്കുന്നത്ഓടിയ്ക്കാനാവൂ. കണ്ടുപിടിയ്ക്കാനുള്ള അംഗത്തെ ഈ അറേയുടെഅടുക്കിലെ നടുവിലെ അംഗവുമായി ഒത്തു നോക്കുന്നു. അവ ഒന്നാണെങ്കിൽ തിരയൽ സാർത്ഥകമായി അവിടെവച്ച് അവസാനിക്കുന്നു. ഇല്ലെങ്കിൽ കണ്ടുപിടിയ്ക്കാനുള്ള അംഗം നടുവിലെ അംഗത്തേക്കാൾ ചെറുതാണോ എന്ന് നോക്കുന്നു. ചെറുതാണെങ്കിൽ അത് അറേയുടെഅടുക്കിന്റെ രണ്ടാമത്തെ പകുതിയിൽ ഉണ്ടാകില്ല എന്ന് ഉറപ്പാണല്ലോ. അഥവാ കണ്ടു പിടിയ്ക്കാനുള്ള അംഗം നടുവിലെ അംഗത്തേക്കാൾ വലുതാണെങ്കിൽ അത് അറേയുടെഅടുക്കിന്റെ ആദ്യ പകുതിയിൽ ഉണ്ടാകില്ല എന്നും ഉറപ്പാണ്. എന്തായാലും അടുത്ത ഘട്ടത്തിൽ ഇവയിൽ ഏതെങ്കിലും ഒരു പകുതി ഉപേക്ഷിയ്ക്കാം. മറ്റേ പകുതി (കുട്ടി അറേഅടുക്ക്) എടുത്തു വീണ്ടും മുകളിൽ പറഞ്ഞ സ്റ്റെപ്പുകൾനിർദ്ദേശങ്ങൾ പിന്തുടരുക. ഒരു ഘട്ടത്തിൽ തെരയുന്ന അംഗം ഏതെങ്കിലും കുട്ടി അറേയുടെഅടുക്കിന്റെ നടുവിൽ കണ്ടെത്തപ്പെടും. അപ്പോൾ തിരയൽ അവസാനിപ്പിയ്ക്കാം. അതല്ലെങ്കിൽ കുട്ടി അറേയുടെഅടുക്കിന്റെ വലുപ്പം 1 ആകുകയും അതിനെ ഇനി രണ്ടായി പകുക്കാൻ സാധിക്കുകയില്ല എന്ന നിലയിൽ എത്തിപ്പെടാം. ഇങ്ങനെ വന്നാൽ അറേയിൽ അംഗത്തെതെരയപ്പെടുന്ന കണ്ടെത്താൻവസ്തു സാധിച്ചില്ലഅടുക്കിലില്ല എന്നർത്ഥം.
ഈ അൽഗോരിതത്തിന്റെ സ്റ്റെപ്പുകൾപടികൾ താഴെ കൊടുത്തിരിയിക്കുന്നു.
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"}}
# ''L'' നു 0 എന്നും ''R'' നു ''n'' − 1 എന്നും വില കൊടുക്കുക.
