二分法的算法步骤是什么?
在有序的有N个元素的数组中查找用户输进去的数据x。
算法如下:
1、确定查找范围front=0,end=N-1,计算中项mid=(front+end)/2。
2、若a[mid]=x或front>=end,则结束查找;否则,向下继续。
3.、若a[mid]<x,说明待查找的元素值只可能在比中项元素大的范围内,则把mid+1的值赋给front,并重新计算mid,转去执行步骤2;若a[mid]>x,说明待查找的元素值只可能在比中项元素小的范围内,则把mid-1的值赋给end,并重新计算mid,转去执行步骤2。
扩展资料
基本思想:假设数据是按升序排序的,对于给定值key,从序列的中间位置k开始比较,
如果当前位置arr[k]值等于key,则查找成功;
若key小于当前位置值arr[k],则在数列的前半段中查找,arr[low,mid-1];
若key大于当前位置值arr[k],则在数列的后半段中继续查找arr[mid+1,high],
直到找到为止,时间复杂度:O(log(n))。
取中点,将区间一分为二;若,则就是方程的根;否则所求根在的左侧或右侧若,则以代替;若,则以代替;
函数F(x)=lnx+2x-6在区间(2,3)内有零点,如果能够将零点所在的范围尽量缩小,在一定精确度下,可以得到零点的近似值。为了方便,用“取中点”地方法逐步缩小零点所在的范围。
取区间(2,3)的中点2.5,用计算器算的f(2.5)约等于-0.084。
因为F(2.5)f(2.75)<0,所以零点在区间(2.5,2075)内,所以零点所在的范围就缩小了。
扩展资料:
当数据量很大适宜采用该方法。采用二分法查找时,数据需是排好序的。
假设数据是按升序排序的,对于给定值key,从序列的中间位置k开始比较
如果当前位置arr[k]值等于key,则查找成功
若key小于当前位置值arr[k],则在数列的前半段中查找,arr[low,mid-1]
若key大于当前位置值arr[k],则在数列的后半段中继续查找arr[mid+1,high]
参考资料来源:百度百科-二分法