二分查找

暑假来总结一下有一些习题板块：

首先就是二分查找，其实以前自己做的时候一些细节的地方似懂非懂，那么这里就对所有的二分来进行一下总结吧！发现了讲得很清楚的博客，分享一下：

https://www.cnblogs.com/luoxn28/p/5767571.html

1、如果x在序列中，则输出x出现的位置，否则输出-1。

int binarySearch(int num){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)>>1;
        if(a[mid]==num) return mid;
        else if(a[mid]<num) l=mid+1;
        else r=mid-1;
    }
    return -1;
}

2、每个询问一个整数x，要你找出x第一次出现的位置，如果没有找到，输出-1。

int binarySearch(int num){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)>>1;
        if(a[mid]>=num) r=mid-1;
        else l=mid+1;
    }
    if(l<=n&&a[l]==num) return l;
    return -1;
}

3、每个询问一个整数x，要你找出x最后一次出现的位置，如果没有找到，输出-1。

int binarySearch(int num){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)>>1;
        if(a[mid]<=num) l=mid+1;
        else r=mid-1;
    }
    if(r>0&&a[r]==num) return r;
    return -1;
}

4、每个询问一个整数x，要你找出最后一个等于或者小于x的元素的位置，如果没有找到，输出-1。

int binarySearch(int num){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)>>1;
        if(a[mid]>num) r=mid-1;
        else l=mid+1;
    }
    if(r>0)  return r;
    return -1;
}

5、每个询问一个整数x，要你找出最后一个小于x的元素的位置，如果没有找到，输出-1。

int binarySearch(int num){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)>>1;
        if(a[mid]>=num) r=mid-1;
        else l=mid+1;
    }
    if(r>0) return r;
    return -1;
}

6、每个询问一个整数x，要你找出第一个等于或大于x的元素的位置，如果没有找到，输出-1。

int binarySearch(int num){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)>>1;
        if(a[mid]<num) l=mid+1;
        else r=mid-1;
    }
    if(l<=n) return l;
    return -1;
}

7、每个询问一个整数x，要你找出第一个大于x的元素的位置，如果没有找到，输出-1。

int binarySearch(int num){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)>>1;
        if(a[mid]<=num) l=mid+1;
        else r=mid-1;
    }
    if(l<=n) return l;
    return -1;
}

看起来其实都是比较相似的，好好区分理解一下，其实还是很可以的，对于返回l还是r,>=还是>等等之类的，好好理解一下

习题练习：

1324 -- 【分治练习】查找最接近的元素
Description
　　在一个非降序列中，查找与给定值最接近的元素。
Input
　　第一行包含一个整数n，为非降序列长度。1 <= n <= 100000。
　　第二行包含n个整数，为非降序列各元素。所有元素的大小均在0-1,000,000,000之间。
　　第三行包含一个整数m，为要询问的给定值个数。1 <= m <= 10000。
　　接下来m行，每行一个整数，为要询问最接近元素的给定值。所有给定值的大小均在0-1,000,000,000之间。
Output
　　m行，每行一个整数，为最接近相应给定值的元素值，保持输入顺序。若有多个值满足条件，输出最小的一个。
Sample Input
3
2 5 8
2
10
5
Sample Output
8
5

查找最接近的元素

//yrnddup c++ code
#include <bits/stdc++.h>
using namespace std;
const int N=100005,inf=0x3f3f3f;
int n,m,a[N];
int binarySearch(int num){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)>>1;
        if(a[mid]<num) l=mid+1;
        else r=mid-1;
    }
    return l;
}
int main()
{
     //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>m;
    int x,res;
    for(int i=1;i<=m;i++){
        scanf("%d",&x);
        if(a[n]<x) printf("%d
",a[n]);
        else if(a[1]>x) printf("%d
",a[1]);
        else{
            int res=binarySearch(x);
            if(x-a[res-1]<=a[res]-x) printf("%d
",a[res-1]);
            else printf("%d
",a[res]);
        }
    }
    return 0;
}
/*
*/

View Code

1325 -- 【分治练习】二分法求函数的零点
Description
　　有函数：f(x)=x^5-15x^4+85x^3-225x^2+274x-121
　　已知f(1.5)>0 ,f(2.4)<0 且方程f(x)=0 在区间[1.5,2.4] 有且只有一个根，请用二分法求出该根。
Input
　　(无)
Output
　　该方程在区间[1.5,2.4]中的根。要求四舍五入到小数点后6位。

二分法求函数的零点

//yrnddup c++ code
#include <bits/stdc++.h>
#define E 1e-8
using namespace std;
double calculate(double x)
{
    return x*x*x*x*x-15*x*x*x*x+85*x*x*x-225*x*x+274*x-121;
}
int main()
{
    double left=1.5,right=2.4;
    while(left+E<=right)
    {
        double mid=(left+right)/2.0;
        if(calculate(mid)>0)
            left=mid;
        else right=mid;
    }
    printf("%.6lf
",left);
//    if(calculate(left)==0)
//        printf("%.6lf
",left);
//    else
//        printf("%.6lf
",left);
    return 0;
}

View Code

还有LIS最长不下降子序列的二分做法，可以看前面的总结