Tìm kiếm nhị phân
Ghi chú và tham khảo > Chú thích

↑  Williams, Jr., Louis F. (ngày 22 tháng 4 năm 1976). A modification to the half-interval search (binary search) method. Proceedings of the 14th ACM Southeast Conference. ACM. tr. 95–101. doi:10.1145/503561.503582. Lưu trữ bản gốc ngày 12 tháng 3 năm 2017. Truy cập ngày 29 tháng 6 năm 2018.
↑  Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Binary search".
↑  Butterfield & Ngondi 2016, tr. 46.
↑  Cormen và đồng nghiệp 2009, tr. 39.
↑  Weisstein, Eric W., "Binary search" từ MathWorld.
1 2  Flores, Ivan; Madpis, George (ngày 1 tháng 9 năm 1971). “Average binary search length for dense ordered lists”. Communications of the ACM. 14 (9): 602–603. Bibcode:1985CACM...28...22S. doi:10.1145/362663.362752. ISSN 0001-0782.
1 2  Knuth 1998, §6.2.1 ("Searching an ordered table"), phân mục "Algorithm B".
↑  Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Algorithm B".
1 2 3  Bottenbruch, Hermann (ngày 1 tháng 4 năm 1962). “Structure and use of ALGOL 60”. Journal of the ACM. 9 (2): 161–221. doi:10.1145/321119.321120. ISSN 0004-5411. Procedure is described at p. 214 (§43), titled "Program for Binary Search".
1 2 3 4 5  Knuth 1998, §6.2.1 ("Searching an ordered table"), phân mục "History and bibliography".
1 2  Kasahara & Morishita 2006, tr. 8–9.
1 2 3 4 5 6  Knuth 1998, §6.2.1 ("Searching an ordered table"), phân mục "Further analysis of binary search".
↑  Knuth 1998, §6.2.1 ("Searching an ordered table"), "Theorem B".
↑  Chang 2003, tr. 169.
1 2 3 4 5 6  Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search".
↑  Shannon, Claude E. (tháng 7 năm 1948). “A Mathematical Theory of Communication”. Bell System Technical Journal. 27 (3): 379–423. doi:10.1002/j.1538-7305.1948.tb01338.x. hdl:11858/00-001M-0000-002C-4314-2.
1 2 3  Knuth 1997, §2.3.4.5 ("Path length").
↑  Knuth 1998, §6.2.1 ("Searching an ordered table"), phân mục "Exercise 23".
↑  Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Exercise 23".
↑  Rolfe, Timothy J. (1997). “Analytic derivation of comparisons in binary search”. ACM SIGNUM Newsletter. 32 (4): 15–19. doi:10.1145/289251.289255.
↑  Khuong, Paul-Virak; Morin, Pat. “Array Layouts for Comparison-Based Searching”. Journal of Experimental Algorithmics. 22. Article 1.3. doi:10.1145/289251.289255.
↑  Knuth 1997, §2.2.2 ("Sequential Allocation").
1 2 3 4  Beame, Paul; Fich, Faith E. (2001). “Optimal bounds for the predecessor problem and related problems”. Journal of Computer and System Sciences. 65 (1): 38–72. doi:10.1006/jcss.2002.1822.
↑  Sedgewick & Wayne 2011, §3.1, subsection "Rank and selection".
↑  Knuth 1998, Answers to Exercises (§6.2.1) cho "Exercise 5".
↑  Knuth 1998, §6.2.1 ("Searching an ordered table").
↑  Knuth 1998, §5.3.1 ("Minimum-Comparison sorting").
↑  Sedgewick & Wayne 2011, §3.2 ("Ordered symbol tables").
↑  Sedgewick & Wayne 2011, §3.2 ("Binary Search Trees"), subsection "Order-based methods and deletion".
↑  Knuth 1998, §6.2.2 ("Binary tree searching"), phân mục "But what about the worst case?".
↑  Sedgewick & Wayne 2011, §3.5 ("Applications"), "Which symbol-table implementation should I use?".
↑  Knuth 1998, §5.4.9 ("Disks and Drums").
↑  Knuth 1998, §6.2.4 ("Multiway trees").
↑  Knuth 1998, §6.4 ("Hashing").
↑  Knuth 1998, §6.4 ("Hashing"), phân mục "History".
↑  Dietzfelbinger, Martin; Karlin, Anna; Mehlhorn, Kurt; Meyer auf der Heide, Friedhelm; Rohnert, Hans; Tarjan, Robert E. (tháng 8 năm 1994). “Dynamic perfect hashing: upper and lower bounds”. SIAM Journal on Computing. 23 (4): 738–761. doi:10.1137/S0097539791194094.
↑  Morin, Pat. “Hash tables” (PDF). tr. 1. Truy cập ngày 28 tháng 3 năm 2016.
↑  Knuth 2011, §7.1.3 ("Bitwise Tricks and Techniques").
1 2  Silverstein, Alan, Judy IV shop manual (PDF), Hewlett-Packard, tr. 80–81
1 2  Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014). Cuckoo filter: practically better than Bloom. Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies. tr. 75–88. doi:10.1145/2674005.2674994.
↑  Bloom, Burton H. (1970). “Space/time trade-offs in hash coding with allowable errors”. Communications of the ACM. 13 (7): 422–426. Bibcode:1985CACM...28...22S. CiteSeerX 10.1.1.641.9096. doi:10.1145/362686.362692.
↑  Knuth 1998, §6.2.1 ("Searching an ordered table"), phân mục "An important variation".
↑  Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Algorithm U".
↑  Moffat & Turpin 2002, tr. 33.
1 2 3  Knuth 1998, §6.2.1 ("Searching an ordered table"), phân mục "Interpolation search".
↑  Knuth 1998, §6.2.1 ("Searching an ordered table"), phân mục "Exercise 22".
↑  Perl, Yehoshua; Itai, Alon; Avni, Haim (1978). “Interpolation search—a log log n search”. Communications of the ACM. 21 (7): 550–553. Bibcode:1985CACM...28...22S. doi:10.1145/359545.359557.
1 2 3  Chazelle, Bernard; Liu, Ding (ngày 6 tháng 7 năm 2001). Lower bounds for intersection searching and fractional cascading in higher dimension. 33rd ACM Symposium on Theory of Computing. ACM. tr. 322–329. doi:10.1145/380752.380818. ISBN 978-1-58113-349-3. Truy cập ngày 30 tháng 6 năm 2018.
↑  Chazelle, Bernard; Liu, Ding (ngày 1 tháng 3 năm 2004). “Lower bounds for intersection searching and fractional cascading in higher dimension” (PDF). Journal of Computer and System Sciences (bằng tiếng Anh). 68 (2): 269–284. CiteSeerX 10.1.1.298.7772. doi:10.1016/j.jcss.2003.07.003. ISSN 0022-0000. Truy cập ngày 30 tháng 6 năm 2018.
↑  Emamjomeh-Zadeh, Ehsan; Kempe, David; Singhal, Vikrant (2016). Deterministic and probabilistic binary search in graphs. 48th ACM Symposium on Theory of Computing. tr. 519–532. arXiv:1503.00805. doi:10.1145/2897518.2897656.
↑  Ben-Or, Michael; Hassidim, Avinatan (2008). “The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well)” (PDF). 49th Symposium on Foundations of Computer Science. tr. 221–230. doi:10.1109/FOCS.2008.58. ISBN 978-0-7695-3436-7.
↑  Pelc, Andrzej (1989). “Searching with known error probability”. Theoretical Computer Science. 63 (2): 185–202. doi:10.1016/0304-3975(89)90077-7.
↑  Rivest, Ronald L.; Meyer, Albert R.; Kleitman, Daniel J.; Winklmann, K. Coping with errors in binary search procedures. 10th ACM Symposium on Theory of Computing. doi:10.1145/800133.804351.
↑  Pelc, Andrzej (2002). “Searching games with errors—fifty years of coping with liars”. Theoretical Computer Science. 270 (1–2): 71–109. doi:10.1016/S0304-3975(01)00303-6.
↑  Rényi, Alfréd (1961). “On a problem in information theory”. Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei (bằng tiếng Hungary). 6: 505–516. MR 0143666.
↑  Høyer, Peter; Neerbek, Jan; Shi, Yaoyun (2002). “Quantum complexities of ordered searching, sorting, and element distinctness”. Algorithmica. 34 (4): 429–448. arXiv:quant-ph/0102078. doi:10.1007/s00453-002-0976-3.
↑  Childs, Andrew M.; Landahl, Andrew J.; Parrilo, Pablo A. (2007). “Quantum algorithms for the ordered search problem via semidefinite programming”. Physical Review A. 75 (3). 032335. arXiv:quant-ph/0608161. Bibcode:2007PhRvA..75c2335C. doi:10.1103/PhysRevA.75.032335.
↑  Grover, Lov K. (1996). A fast quantum mechanical algorithm for database search. 28th ACM Symposium on Theory of Computing. Philadelphia, PA. tr. 212–219. arXiv:quant-ph/9605043. doi:10.1145/237814.237866.
↑  Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "History and bibliography".
↑  Peterson, William Wesley (1957). “Addressing for random-access storage”. IBM Journal of Research and Development. 1 (2): 130–146. doi:10.1147/rd.12.0130.
↑  "2n−1". OEIS A000225 Lưu trữ 2016-06-08 tại Wayback Machine.  Truy cập ngày 7 tháng 5 năm 2016.
↑  Lehmer, Derrick (1960). Teaching combinatorial tricks to a computer. Proceedings of Symposia in Applied Mathematics. 10. tr. 180–181. doi:10.1090/psapm/010.
↑  Chazelle, Bernard; Guibas, Leonidas J. (1986). “Fractional cascading: I. A data structuring technique” (PDF). Algorithmica. 1 (1–4): 133–162. CiteSeerX 10.1.1.117.8349. doi:10.1007/BF01840440.
↑  Chazelle, Bernard; Guibas, Leonidas J. (1986), “Fractional cascading: II. Applications” (PDF), Algorithmica, 1 (1–4): 163–191, doi:10.1007/BF01840441
↑  “bsearch – binary search a sorted table”. The Open Group Base Specifications (ấn bản thứ 7). The Open Group. 2013. Lưu trữ bản gốc ngày 21 tháng 3 năm 2016. Truy cập ngày 28 tháng 3 năm 2016.
↑  Stroustrup 2013, tr. 945.
↑  Unisys (2012), COBOL ANSI-85 programming reference manual, 1, tr. 598–601
↑  “Package sort”. The Go Programming Language. Lưu trữ bản gốc ngày 25 tháng 4 năm 2016. Truy cập ngày 28 tháng 4 năm 2016.
↑  “java.util.Arrays”. Java Platform Standard Edition 8 Documentation. Oracle Corporation. Lưu trữ bản gốc ngày 29 tháng 4 năm 2016. Truy cập ngày 1 tháng 5 năm 2016.
↑  “java.util.Collections”. Java Platform Standard Edition 8 Documentation. Oracle Corporation. Lưu trữ bản gốc ngày 23 tháng 4 năm 2016. Truy cập ngày 1 tháng 5 năm 2016.
↑  “List<T>.BinarySearch method (T)”. Microsoft Developer Network. Lưu trữ bản gốc ngày 7 tháng 5 năm 2016. Truy cập ngày 10 tháng 4 năm 2016.
↑  “NSArray”. Mac Developer Library. Apple Inc. Lưu trữ bản gốc ngày 17 tháng 4 năm 2016. Truy cập ngày 1 tháng 5 năm 2016.
↑  “CFArray”. Mac Developer Library. Apple Inc. Lưu trữ bản gốc ngày 20 tháng 4 năm 2016. Truy cập ngày 1 tháng 5 năm 2016.
↑  “8.6. bisect — Array bisection algorithm”. The Python Standard Library. Python Software Foundation. Lưu trữ bản gốc ngày 25 tháng 3 năm 2018. Truy cập ngày 26 tháng 3 năm 2018.
↑  Fitzgerald 2007, tr. 152.