二分查找（递归）

int BSearch(int a[],int x,int low,int high)
{
    int mid;
    if(low > high)
        return -1;
    mid = (low + high) / 2;
    if(a[mid] == x)
        return mid;
    else if(a[mid] > x)
        BSearch(a,x,low,mid-1);
    else
        Bsearch(a,x,mid+1,high);
}

非递归

int BSearch(int a[],int x,int n)
{
    int low=0;
    int high=n-1;
    while(low <= high)
    {
        int mid = (low+high)/2;
        if(a[mid]==x)
            return mid;
        else if(a[mid]>x)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

分治法下用递归解决问题用主定理