ಬೈನರಿ ಸರ್ಚ್ ಆಲಗೋರಿತಮ್: ಪರಿಷ್ಕರಣೆಗಳ ನಡುವಿನ ವ್ಯತ್ಯಾಸ

ಬೈನರಿ ಹುಡುಕಾಟವು ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ಲಾಗರಿಥಮಿಕ್ ಸಮಯದಲ್ಲಿ ಚಲಿಸುತ್ತದೆ ಮತ್ತು <math>O(\log n)</math> ಹೋಲಿಕೆಗಳನ್ನು ಮಾಡುತ್ತದೆ, ಇಲ್ಲಿ <math>O</math> ಎಂಬುದು ಶ್ರೇಣಿಯಲ್ಲಿನ ಅಂಶಗಳ ಸಂಖ್ಯೆ ಮತ್ತು <math>\log</math> ಎಂಬುದು ಲಾಗರಿಥಮ್ ಆಗಿದೆ. <ref name="FloresMadpis1971">{{cite journal|last1=Flores|first1=Ivan|last2=Madpis|first2=George|title=Average binary search length for dense ordered lists|journal=ಕಮ್ಯುನಿಕೇಶನ್ಸ್ ಆಫ್ ಎಸಿಎಂ|date=1 September 1971|volume=14|issue=9|pages=602–603|issn=0001-0782|doi=10.1145/362663.362752|bibcode=1985CACM...28...22S}}</ref> ಸಣ್ಣ ಸರಣಿಗಳನ್ನು ಹೊರತುಪಡಿಸಿ ಬೈನರಿ ಹುಡುಕಾಟ ರೇಖೀಯ ಹುಡುಕಾಟಕ್ಕಿಂತ ವೇಗವಾಗಿರುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಬೈನರಿ ಹುಡುಕಾಟವನ್ನು ಅನ್ವಯಿಸಲು ಶ್ರೇಣಿಯನ್ನು ಮೊದಲು ವಿಂಗಡಿಸಬೇಕು. ವೇಗದ ಹುಡುಕಾಟಕ್ಕಾಗಿ ವಿನ್ಯಾಸಗೊಳಿಸಲಾದ ವಿಶೇಷ ದತ್ತಾಂಶ ರಚನೆಗಳಿವೆ, ಉದಾಹರಣೆಗೆ ಹ್ಯಾಶ್ ಕೋಷ್ಟಕಗಳು, ಬೈನರಿ ಹುಡುಕಾಟಕ್ಕಿಂತ ಹೆಚ್ಚು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಹುಡುಕಬಹುದು. ಬೈನರಿ ಹುಡುಕಾಟವನ್ನು ವ್ಯಾಪಕ ಶ್ರೇಣಿಯ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಲು ಬಳಸಬಹುದು.

 

==ಆಲಗೋರಿತಮ್==

ಬೈನರಿ ಹುಡುಕಾಟ ವಿಂಗಡಿಸಲಾದ ಅರ್ರೆಗಳಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ರಚನೆಯ ಮಧ್ಯದಲ್ಲಿರುವ ಒಂದು ಅಂಶವನ್ನು ಗುರಿ ಮೌಲ್ಯದೊಂದಿಗೆ ಹೋಲಿಸುವ ಮೂಲಕ ಬೈನರಿ ಹುಡುಕಾಟ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ. ಗುರಿ ಮೌಲ್ಯವು ಅಂಶಕ್ಕೆ ಹೊಂದಿಕೆಯಾದರೆ, ರಚನೆಯಲ್ಲಿ ಅದರ ಸ್ಥಾನವನ್ನು ಹಿಂತಿರುಗಿಸಲಾಗುತ್ತದೆ. ಗುರಿ ಮೌಲ್ಯವು ಅಂಶಕ್ಕಿಂತ ಕಡಿಮೆಯಿದ್ದರೆ, ಹುಡುಕಾಟವು ರಚನೆಯ ಕೆಳಗಿನ ಅರ್ಧಭಾಗದಲ್ಲಿ ಮುಂದುವರಿಯುತ್ತದೆ. ಗುರಿ ಮೌಲ್ಯವು ಅಂಶಕ್ಕಿಂತ ಹೆಚ್ಚಿದ್ದರೆ, ರಚನೆಯ ಮೇಲಿನ ಅರ್ಧಭಾಗದಲ್ಲಿ ಹುಡುಕಾಟ ಮುಂದುವರಿಯುತ್ತದೆ. ಇದನ್ನು ಮಾಡುವುದರ ಮೂಲಕ, ಅಲ್ಗಾರಿದಮ್ ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲೂ ಗುರಿ ಮೌಲ್ಯವು ಸುಳ್ಳಾಗದ ಅರ್ಧವನ್ನು ತೆಗೆದುಹಾಕುತ್ತದೆ.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Algorithm B"}}