有一个由4000个整数构成的顺序表，假定表中的元素已经按升序排列，采用二分查找定位一个元素。则最多需要几

Question

有一个由4000个整数构成的顺序表，假定表中的元素已经按升序排列，采用二分查找定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素：
我找到了有关的解释
2^11-1=2047 2^12-1=4095 2047<4000<4095 故树的高度为12

但我看不懂，能用一种让中学生看懂的思路讲解一下吗，弄懂后还有分送！

Answer 1

二分查找 看名字 理解意思就是
每次把你需要查找的数组分成基本平均的2部分，然后看两部分中间的那个数是不是我们要找的数。假如不是我们要找的数，那么我们看这个数是比我们的大呢还是比我们要找的数小，假如说中间这个数比我们要找的数小 那么我们要找的数是不是应该在比较大的那一部分，如果中间这个数比我们要找的数更大，那么我们要找的数应该是在比较小的那一部分的。
然后继续按照我们刚才的方法来处理刚才挑选出来的这一个部分，最不理想的情况就是：你最后把这个数组已经分到了最小的部分（一个部分就只有一个数值的时候）了，那么这个时候你一比较 就知道最后这个数就是我们要找的数了（当然 也有可能根本找不到我们要找的那个数，这种时候 说明我们这个数组里面根本就没有我们要找的这个数）。
OK了吗？
再给你举个例子吧
我们现在有一个已经排序好了的数组（顺序表） 如下
1 2 3 5 8 9 12 45 69 85 99 102 103
这个数组总共有13个数字（如果我没有数错的话）
现在我们要在其中找到5这个数字
那么我们首先把这个数组分成两个部分（以最中间的那个数为界限）我们用这个数组的长度13/2=6.5 进一法 取值为7
所以我们把第七个元素作为我们这一轮的判断标准
第七个元素=12
我们拿5（要查找的数） 和12（中间数）比较，发现5比12小 所以我们要找的数字应该是在我们12的前面的
那我们现在就只需要对1-6这六个元素进行刚才的过程了
1-6总共包含了6个元素 我们用刚才的方法取出一个值来进行比较
6/2=3 这里进一法不起作用了
我们把3号元素作为我们查找的对比项
比较5 （要查找的数）和3号元素3（中间数也就是比较项）进行比较 发现5>3 所以我们知道我们要找的数应该是在这个范围内 3的后面的
所以现在我们可以进一步确定我们要找的数的范围是 4-6这个范围了
那么我们在4-6这个范围进行查找 共3项 3/2=1.5 进一法为2 所以我们以这个范围内第二个项为中间项进行比较 也就是第5项 数值为8 我们比较5和8 发现5比8更小
所以我们确定我们要找的数应该在4-4这个范围内 （虽然说我们人是可以判断了 但是计算机还不行哦 我们这些程序都是给计算机用的 所以我们下面的步骤还得进行下去）
4-4这个范围内总共有一项 1/2=0.5 进一法为1
所以我们确定要作比较的项应该为这个范围内的第一项 也就是第四项 数值取出来为5 拿5（要找的数值）和5（中间项）进行比较 发现5=5 此时说明我们本次查找的目的达到了 找到了相同的项 我们的查找就此结束
就此推论 你可以想象
应该可以总结一张表出来
查找数组总个数 需要查找的最多次数
1个 1
2-3个 2
4-7个 3
8-15个 4
16-31个 5
32-63个 6
………………………………………………………………

（如果你通过此次回答解决问题 希望你采纳答案 如果没解决 请继续在这里发问 如果是成都本地的 可以在这里留言说是成都本地人 可以来我家教中心 我当面给你讲（讲这个不收费））

Answer 2

意思就是如果有2047个数，二分查找定位一个数最多需要11次（2^11-1=2047，2的11次幂减1是2047），同理在4096个数中定位一个数最多需要12次（2^12是12个2相乘）。因为2047<4000<4096，所以在4000个数中定位一个数最多需要的次数比11多，不大于12，而且肯定是整数，所以只能是12次。

Answer 3

升序排列，将表等分为二，假设所要查找的元素为A，将A与表中间的数作比较，若中间的数等于A，查找完毕；若中间的数小于A，那么表的前半部分所有元素均小于A，A必然在表的后半部分；将后半部分的所有元素当作一个新表，再对它做同样的处理。若中间的数大于A，那么处理前半个表。求取最大比较次数，那么要求所有的元素都进行过排除，进行n次比交后剩余未进行比较排除的元素数最多为M/2^n向上取整（M为总个数），最终除法运算结果小于时比较完毕。因此，只进行n次比较最多能确定2^n-1个元素中是否存在所需元素。

Answer 4

呵呵，这个像数据结构里的二叉树，先找中间那个数，如果要找的数比他小，就向左查找，反之向右查找，这样依次迭代，就可见次数肯定是2的指数幂啊，2^11-1=2047， 2^12-1=4095，2047<4000<4095 所以应该是12次啊。

Answer 5

所谓二分法，每次都与中间数值比较大小，由于大小顺序一定，所以可以根据目标值与中间数字的大小关系确定，目标在中间值的前边还是后边，然后再取前半部的中间值（或者后半部的中间值）比较，以此循环，直至找到为止，次数最多就是找完以后发现不存在这个数，所以次数与2的多少次幂有关系，你可以先用10以内的画图看一下就发现规律了，看百度百科里二分法的解释可以