NOIP 普及组初赛 · NOIP 2009 普及组初赛试题 第 16 题

有一个由 $4000$ 个整数构成的顺序表，假定表中的元素已经按升序排列，采用二分查找定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素：

二分查找每次把范围砍掉一半，最多比较次数就是⌊log₂n⌋+1。n=4000时，先算log₂4000≈11.96，向下取整得11，再加1就是12次。

很多学生看到4000接近2^12=4096，就脱口而出12次，这没错，但如果用计算器直接算log₂4000≈11.96，取整时容易搞混是向上还是向下。记住二分查找最坏情况是⌊log₂n⌋+1，不是⌈log₂(n+1)⌉，虽然数值上经常一样，但公式要背准。还有人会误以为4000刚好能分12次，其实2^11=2048，第一次分完只剩2048，第二次分完1024……第11次分完1，第12次分完0，所以确实是12次。

这道题考什么

二分查找（折半查找）的最坏比较次数。

概念：二分查找是怎么“砍半”的

把有序数组当成一根绳子，每次对折，只保留一半继续找。每折一次，可能性就减半。对n个元素，最多折几次能把范围缩到0？答案是⌊log₂n⌋+1次。

• 答案：B（12次）

以上为完整解析的章节结构，展开每一步的推导、正确性说明与复杂度分析请在平台查看。