关于折半查找比较次数如何计算的问题

Question

顺序表中有1000个元素，用折半查找时，最大比较次数为  几次？

Answer 1

有序的顺序表的话，由折半查找法的定义本身，每次比较之后问题规模都会减小一半，当pow(2, k)恰好等于N时，查找规模可以说已经是0了，所以折半查找的最大比较次数应当是floor(k) + 1,其中k满足2^k=N。 其中对于任意二分查找，其比较次数都在[1, floor(k)+1]之间，当N=1000时，最大比较次数为11