呵呵,这个像数据结构里的二叉树,先找中间那个数,如果要找的数比他小,就向左查找,反之向右查找,这样依次迭代,就可见次数肯定是2的指数幂啊,2^11-1=2047,2^12-1=4095,2047
所谓二分法,每次都与中间数值比较大小,由于大小顺序一定,所以可以根据目标值与中间数字的大小关系确定,目标在中间值的前边还是后边,然后再取前半部的中间值(或者后半部的中间值)比较,以此循环,直至找到为止,次数最多就是找完以后发现不存在这个数,所以次数与2的多少次幂有关系,你可以先用10以内的画图看一下就发现规律了,看百度百科里二分法的解释可以
二分查找看名字理解意思就是
每次把你需要查找的数组分成基本平均的2部分,然后看两部分中间的那个数是不是我们要找的数。假如不是我们要找的数,那么我们看这个数是比我们的大呢还是比我们要找的数小,假如说中间这个数比我们要找的数小那么我们要找的数是不是应该在比较大的那一部分,如果中间这个数比我们要找的数更大,那么我们要找的数应该是在比较小的那一部分的。
然后继续按照我们刚才的方法来处理刚才挑选出来的这一个部分,最不理想的情况就是:你最后把这个数组已经分到了最小的部分(一个部分就只有一个数值的时候)了,那么这个时候你一比较就知道最后这个数就是我们要找的数了(当然也有可能根本找不到我们要找的那个数,这种时候说明我们这个数组里面根本就没有我们要找的这个数)。
OK了吗?
再给你举个例子吧
我们现在有一个已经排序好了的数组(顺序表)如下
1235891245698599102103
这个数组总共有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
………………………………………………………………
(如果你通过此次回答解决问题希望你采纳答案如果没解决请继续在这里发问如果是成都本地的可以在这里留言说是成都本地人可以来我家教中心我当面给你讲(讲这个不收费))
意思就是如果有2047个数,二分查找定位一个数最多需要11次(2^11-1=2047,2的11次幂减1是2047),同理在4096个数中定位一个数最多需要12次(2^12是12个2相乘)。因为2047
升序排列,将表等分为二,假设所要查找的元素为A,将A与表中间的数作比较,若中间的数等于A,查找完毕;若中间的数小于A,那么表的前半部分所有元素均小于A,A必然在表的后半部分;将后半部分的所有元素当作一个新表,再对它做同样的处理。若中间的数大于A,那么处理前半个表。求取最大比较次数,那么要求所有的元素都进行过排除,进行n次比交后剩余未进行比较排除的元素数最多为M/2^n向上取整(M为总个数),最终除法运算结果小于时比较完毕。因此,只进行n次比较最多能确定2^n-1个元素中是否存在所需元素。