二分法

数学领域术语

二分法是指对于区间[a，b]上连续不断且f（a）·f（b）<0的函数y=f（x），通过不断地把函数f（x）的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法。

基本信息

1/3

二分法（Bisection method）即一分为二的方法. 设[a，b]为R的闭区间. 逐次二分法就是造出如下的区间序列([an，bn])：a0=a，b0=b，且对任一自然数n，[an+1，bn+1]或者等于[an，cn]，或者等于[cn，bn]，其中cn表示[an，bn]的中点.

由于计算过程的具体运算复杂，但每一步的方式相同，所以可通过编写程序来运算。

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]<aim){

start = mid+1;

}

mid = (start+end)/2;//b，注意a，b

}

return (data[mid]!=aim)?-1:mid;//返回结果