[如何运用二分法思想写程序扫描呢]二分法求 sin(x)-x*x/4=0的近似解#include#includemain(){FILE *fp;int k=0;double a=1.5,b=2,x;fp=fopen(＂nt＂,＂w＂);while((b-a)>0.01){x=(a+b)/2;fprintf(fp,＂\n\nk=%d ＂,k);fpr...+阅读

网页链接

你可以看看我的上面这个博客

由于二分查找每次查询都是从数组中间切开查询，所以每次查询，剩余的查询数为上一次的一半，从下表可以清晰的看出查询次数与剩余元素数量对应关系

表-查询次数及剩余数

第几次查询 剩余待查询元素数量

1 N/2

2 N/(2^2)

3 N/(2^3)

… …

K N/(2^K)

从上表可以看出N/(2^K)肯定是大于等于1，也就是N/(2^K)>=1，我们计算时间复杂度是按照最坏的情况进行计算，也就是是查到剩余最后一个数才查到我们想要的数据，也就是

N/(2^K)=1

=>N=2^K

=>K=log2N

所以二分查找的时间复杂度为O(log2N)