设查找表中有100个元素,如果用二分法查找数据元素X,最多需比较多少次?

设查找表中有100个元素,如果用二分法查找数据元素X,最多需比较多少次?
设查找表中有100个元素,如果用二分法查找数据元素X,最多需比较多少次?

设查找表中有100个元素,如果用二分法查找数据元素X,最多需比较多少次?
最多需要7次,可以根据二叉搜索树判断,最多为log(n,2) + 1次.

二分法目录
数学方面
求法
计算机应用Java语言
C语言
C++语言
C++语言中的二分查找法
MATLAB语言
经济学方面
哲学方面
一般使用方面数学方面
求法
计算机应用 Java语言
C语言
C++语言
C++语言中的二分查找法
MATLAB语言

全部展开

二分法目录
数学方面
求法
计算机应用Java语言
C语言
C++语言
C++语言中的二分查找法
MATLAB语言
经济学方面
哲学方面
一般使用方面数学方面
求法
计算机应用 Java语言
C语言
C++语言
C++语言中的二分查找法
MATLAB语言
经济学方面
哲学方面
一般使用方面
展开 编辑本段数学方面
一般地，对于函数f(x),如果存在实数c,当x=c时，若f(c)=0,那么把x=c叫做函数f(x)的零点。 解方程即要求f(x)的所有零点。 假定f(x)在区间（x，y）上连续 先找到a、b属于区间（x，y），使f(a)，f(b)异号，说明在区间(a,b)内一定有零点，然后求f[(a+b)/2], 现在假设f(a)<0,f(b)>0,a①如果f[(a+b)/2]=0，该点就是零点， 如果f[(a+b)/2]<0,则在区间（(a+b)/2，b)内有零点，(a+b)/2=>a，从①开始继续使用 中点函数值判断。 如果f[(a+b)/2]>0，则在区间(a,(a+b)/2)内有零点，(a+b)/2<=b，从①开始继续使用 中点函数值判断。 这样就可以不断接近零点。 通过每次把f(x)的零点所在小区间收缩一半的方法，使区间的两个端点逐步迫近函数的零点，以求得零点的近似值，这种方法叫做二分法。 从以上可以看出，每次运算后，区间长度减少一半，是线形收敛。另外，二分法不能计算复根和重根。
编辑本段求法
给定精确度ξ,用二分法求函数f(x)零点近似值的步骤如下: 1 确定区间[a,b],验证f(a)·f(b)<0,给定精确度ξ. 2 求区间(a,b)的中点c. 3 计算f(c). (1) 若f(c)=0,则c就是函数的零点; (2) 若f(a)·f(c)<0,则令b=c; (3) 若f(c)·f(b)<0,则令a=c. (4) 判断是否达到精确度ξ:即若┃a-b┃<ξ,则得到零点近似值a(或b),否则重复2-4.
编辑本段计算机应用
由于计算过程的具体运算复杂，但每一步的方式相同，所以可通过编写程序来运算。
Java语言
public int binarySearch(int[] data,int aim){//以int数组为例，aim为需要查找的数 int start = 0; int end = data.length-1; int mid = (start+end)/2;//a while(data[mid]!=aim&&end>start){//如果data[mid]等于aim则死循环，所以排除 if(data[mid]>aim){ end = mid-1; }else if(data[mid]C语言
方程式为：f(x) = 0，示例中f(x) = 1+x-x^3 使用示例： input a b e: 1 2 1e-5 solution: 1.32472 源码如下： #include #include #include #include double f(double x) { return 1+x-x*x*x; } int main() { double a = 0, b = 0, e = 1e-5; printf("input a b e: "); scanf("%lf%lf%lf", &a, &b, &e); e = fabs(e); if (fabs(f(a)) <= e) { printf("solution: %lg\n", a); } else if (fabs(f(b)) <= e) { printf("solution: %lg\n", b); } else if (f(a)*f(b) > 0) { printf("f(%lg)*f(%lg) > 0 ! need <= 0 !\n", a, b); } else { while (fabs(b-a) > e) { double c = (a+b)/2.0; if (f(a)* f ( c ) < 0) b = c; else a = c; } printf("solution: %lg\n", (a+b)/2.0); } return 0; }
C++语言
[类C编写]. |f(x)|<10^-5 f(x)=2x^3-4x^2+3x-6 #include"iostream" #include"stdio.h" #include"math.h" #define null 0 double fx(double); //f(x)函数 void main() { double xa(null),xb(null),xc(null); do { printf("请输入一个范围x0 x1："); std::cin>>xa>>xb; //输入xa xb的值 printf("%f %f",xa,xb); } while(fx(xa)*fx(xb)>=0); //判断输入范围内是否包含函数值0 do { if(fx((xc=(xa+xb)/2))*fx(xb)<0) //二分法判断函数值包含0的X取值区间 { xa=xc; } else { xb=xc; } } while(fx(xc)>pow(10.0,-5)||fx(xc)<-1*pow(10.0,-5));//判断x根是否在接近函数值0的精确范围内 printf("\n 得数为：%f",xc); } double fx(double x) { return(2.0*pow(x,3)-4.0*pow(x,2)+3*x-6.0); }
C++语言中的二分查找法
算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。 基本思想：假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找 ，直到找到为止。 假如有一组数为3，12，24，36，55，68，75，88要查给定的值24.可设三个变量front，mid，end分别指向数据的上界，中间和下界，mid=（front+end）/2. 1.开始令front=0（指向3），end=7（指向88），则mid=3（指向36）。因为mid>x，故应在前半段中查找。 2.令新的end=mid-1=2，而front=0不变，则新的mid=1。此时x>mid，故确定应在后半段中查找。 3.令新的front=mid+1=2，而end=2不变，则新的mid=2，此时a[mid]=x，查找成功。 如果要查找的数不是数列中的数，例如x=25，当第三次判断时，x>a[mid]，按以上规律，令front=mid+1，即front=3，出现front>end的情况，表示查找不成功。 例：在有序的有N个元素的数组中查找用户输进去的数据x。 算法如下： 1.确定查找范围front=0，end=N-1，计算中项mid（front+end）/2。 2.若a[mid]=x或front>=end,则结束查找；否则，向下继续。 3.若a[mid]x，说明待查找的元素值只可能在比中项元素小的范围内，则把mid-1的值赋给end，并重新计算mid，转去执行步骤2。 代码： #include #define N 10 using namespace std; int main() { int a[N],front,end,mid,x,i; cout<<"请输入已排好序的a数组元素:"<>a[i]; cout<<"请输入待查找的数x:"<>x; front=0; end=N-1; mid=(front+end)/2; while(frontx)end=mid-1; mid=front + (end - front)/2; } if(a[mid]!=x) cout<<"没找到！"<MATLAB语言
function y=f(x) y=f(x); %函数f(t)的表达式 i=0; %二分次数记数 a=a; %求根区间左端 b=b; %求根区间右端 fa=f(a); %计算f(a)的值 fb=f(b); %计算f(b)的值 c=(a+b)/2; %计算区间中点 fc=f(c); %计算区间中点f(c) while abs(fc)>=ε; %判断f(c)是否为零点 if fa*fc>=0; %判断左侧区间是否有根 fa=fc; a=c; else fb=fc; b=c; end c=(a+b)/2; fc=f(c); i=i+1; end fprintf('\n%s%.6f\t%s%d','c,'迭代次数i=',i) %计算结果输出
编辑本段经济学方面
传统的经济学家把经济分为实物经济和货币经济两部分，其中，经济理论分析实际变量的决定，而货币理论分析价格的决定，两者之间并没有多大的关系，这就是所谓的二分法。
编辑本段哲学方面
又称二分说，爱利亚学派芝诺四大著名悖论之一 证明运动是不可能的。 其主要思路是：假设一个存在物经过空间而运动，为了穿越某个空间，就必须穿越这个空间的一半。为了穿越这一半，就必须穿越这一半的一半；以此类推，直至无穷。所以，运动是不可能的。
编辑本段一般使用方面
即将所有的事物根据其属性分成两种。错误的分类可能导致逻辑谬论，如：非黑即白，不是忠的就是奸的。这很明显忽略了中间状态的存在。正确的分类法应如：白-非白。

收起