二分法

• 求方程的根

# include<iostream>
# include<cmath>
//double 不用==
#define EPS 1e-6
using namespace std;

double f(double x){
    return (pow(x,3)-5*pow(x,2)+10*x-80);
}
int main(){
    double L = 0,R = 100;
    //不用(L+R)/2是为了避免溢出
    double mid = L +(R-L)/2;
    //time是迭代次数
    int time = 1;
    while(fabs(f(mid)) >= EPS){
        if(f(mid) > 0){
            R = mid;
            mid = L + (R-L)/2;
            time++;
        }
        if(f(mid) < 0){
            L = mid;
            mid = L +(R-L)/2;
            time++;
        }
    }
    cout << "Time " << time << endl;
    cout << "root" << mid << endl;
    return  0;
}

• 寻找指定和的整数对

# include<iostream>
using namespace std;
int data[100];
int N;
//排序——快速排序
void swap(int &x,int &y){
    int temp;
    temp = x;
    x = y;
    y = temp;
}
//快排
void QuickSort(int a[],int start,int end){
    if(end <= start) return;
    int L = start,R = end;
    int k = a[L];
    if(start != end ){
        while(a[R] >= k && L < R){
            R--;
        }
        swap(a[R],a[L]);
        while(a[L] <= k && L < R){
            L++;
        }
        swap(a[R],a[L]);
    }
    QuickSort(a,start,L-1);
    QuickSort(a,L+1,end);
}
//分治寻找a[]内和为m的数
void search(int a[],int m){
    int L = 0,R = N-1;
    for(int i = 0;i<N;i++){
        int k = m-a[i];
        int mid = N/2;
        if(a[mid] != k && L < R ){
            if(a[mid] > k){
                R = mid;
                mid = L+(R-L)/2;
            }
            while(a[mid] < k){
                L = mid;
                mid = L +(R-L)/2;
            }
        }if(a[mid] == k && mid != i){
            cout << mid << '+' << i << endl;
        }
    }
}
int main(){
    int m;
    cin >> N >> m;
    for(int i = 0;i<N;i++){
        cin >> data[i];
    }
    QuickSort(data,0,N-1);
    search(data,m);
}