查找 —— 二分查找

【概述】

二分查找是十分常见的问题，其与各种算法的结合比较密切，关于其原理：点击这里

除了查找元素、查找连续函数外，还可以使用 STL 容器中的 lower_bound()、upper_bound()、lower_bound()、upper_bound() 函数，具体使用：点击这里

【实现】

1.查找元素

int BinarySearch(int a[],int x,int x){
    int left,right,mid;
    int res=-1;
    
    left=0;//left为集合下界
    right=n-1//right为集合上界
    
    while(left<=right){
        mid=(left+right)/2;//设置中值
        if(num[mid]==x){//查找到符合元素x
            res=mid;
            break;
        }
        else if(num[mid]<x)//x在右边部分
           low=mid+1;//调整集合下界
        else//x在左边部分
           high=mid-1;//调整集合上界
    }
    return res;//若未找到x，则res= -1
}

2.查找连续函数

bool cal(int x){
    ...
}
int BinarySearch(double low,double high){//low为区间下界，high为区间上界
    double left,right,mid;
    left=low;//设置当前查找区间上界的初值
    right=high;//设置当前查找区间下界的初值
    
	while(right-left>1.0e-6){
        mid=(right+left)/2;//设置中值
        if(cal(mid)<x)//函数结果小于带查找的值
            left=mid;//说明在右边部分，调整集合下界
        else
            right=mid;//说明在左边部分，调整集合上界
    }
    return mid;
}

【例题】

1. Can you solve this equation?（HDU-2199）：点击这里
2. 二分法求函数的零点（信息学奥赛一本通-T1241）：点击这里
3. Block Towers（CF-626C）：点击这里
4. Pie（HDU-1969）：点击这里
5. Cable master（HDU-1551）：点击这里
   同题：网线主管（信息学奥赛一本通-T1242）：点击这里
6. Aggressive cows（POJ-2456）：点击这里
7. 丢瓶盖（洛谷-P1316）：点击这里
8. Go Home（AtCoder-2354）(二分+前缀和)：点击这里
9. Artificial Lake（POJ-3658）(二分+结构体)：点击这里
10. Monthly Expense（ POJ-3273）(最小组数和)：点击这里
    同题：月度开销（信息学奥赛一本通-T1243）：点击这里
11. River Hopscotch（POJ-3258）(排序+二分)：点击这里
    同题：河中跳房子（信息学奥赛一本通-T1247）：点击这里
12. The hat（CF-1020D）(查找连续函数+格式控制输出)：点击这里
13. 数列分段`Section II`（洛谷-P1182）(查找连续函数+累加和)：点击这里
14. 一元三次方程求解（信息学奥赛一本通-T1238）(二分求根)：点击这里
15. 查找最接近的元素（信息学奥赛一本通-T1240）(绝对值比较+二分)：点击这里
16. 膨胀的木棍（信息学奥赛一本通-T1246）(数学推导圆心角+二分)：点击这里
17. Gadgets for dollars and pounds（CF-609D）(二分+贪心)：点击这里
18. 炫酷划线（2019牛客寒假算法基础集训营 Day5-E）(二分+栈)：点击这里
19. Median（POJ-3579）(两次二分)：点击这里
20. Can you find it?（HDU-2141）(三数求和+二分)：点击这里
21. 只包含因子 2 3 5 的数（51Nod-1010）(打表+二分)：点击这里