二分法

1、基于：分治策略
2、应用：有序序列
3、隐喻：二叉树
4、时间复杂度：O(logn)
5、关键字：scope

	/**
	 * @param 数组a
	 * @param 目标值target
	 * @return 位序
	 */
	public static int binarySearch(int[] a, int target) {
		int left = 0;
		int right = a.length - 1;  //游标
   
		while (left <= right)      //范围a[left:right]
		{
			int middle = (left + right) / 2;  //取下整
			if (target == a[middle])
				return middle;
			else if (target < a[middle])
				right = middle - 1;  //*明确边界   
			else
				left = middle + 1;   //*~
		}
		return -1;
	}

关键点：
    二分法算法描述简单，但关于scope的划分，边界的问题，理解透彻，对于别的类似问题就得心应手。

1、游标:
         a[left:right] --闭区间，一个scope
2、下整：middle = (left+right)/2 --当scope变为2时，middle落在left上
3、闸门：while(left<=right)
        若target不在a中，最后一次循环中左右游标交叉，则target在区间   (right,left)中。可以修改算法，返回right&left。 
4、初始范围:a[0:n-1]
    进入循环：a[left:right]
   循环中，a[left:right]被分为三段:a[left:middle-1],a[middle],a[middle+1,right]，边界要确保不重复，scope分明，就不会出现死循环。
  
    每步while循环，scope都会缩小，最终会到达闸门left=right(或提前找到结果)；
                                    --算法会在有限步内终止   log(n)
    并且确保target要在新的scope中。
                                    --不会漏掉target



关键字：离散序列，连续序列


数学方面： --百度百科

一般地，对于函数f(x),如果存在实数c,当x=c时f(c)=0,那么把x=c叫做函数f(x)的零点。
　　解方程即要求f(x)的所有零点。
　　先找到a、b，使f(a)，f(b)异号，说明在区间(a,b)内一定有零点，然后求f[(a+b)/2],
　　现在假设f(a)<0,f(b)>0,a<b
　　①如果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.

　例:(C语言)
　　方程式为：f(x) = 0，示例中f(x) = 1+x-x^3
　　使用示例：
　　input a b e: 1 2 1e-5
　　solution: 1.32472

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>

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("solutionL:%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;
}