#83. 美人松的高度2

题目链接：http://oj.tfls.net/p/83

写法一：找到第一个k和最后一个k的位置，区间长度=尾地址-首地址+1；

#include<bits/stdc++.h>
using namespace std;
int ans;
int a[10000010];

//返回第一个p的位置，如不存在p，返回0 
int bs1(int l,int r,int p){
    ans=0;  //答案初始化为0 
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]>=p){   //满足条件，区间向左侧缩 
            if(a[mid]==p) ans=mid;   //相等时才记录答案 
            r=mid-1;
        }
        else
            l=mid+1;
    }
    return ans;
}

//返回最后一个p的位置，如不存在p，返回0 
int bs2(int l,int r,int p){
    ans=0;  //答案初始化为0 
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]<=p){  //满足条件，区间向右侧缩 
            if(a[mid]==p) ans=mid;  //相等时才记录答案 
            l=mid+1;
        }
        else
            r=mid-1;
    }
    return ans;//返回值为-1表示数列中所有数都>P
}

int main(){
    int n,m,k;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        cin>>k;
        if(bs1(1,n,k))  //返回值为真，k存在 
            cout<<bs2(1,n,k)-bs1(1,n,k)+1<<" ";
        else cout<<0<<" ";
    }
    return 0;
}

写法二：找到第一个k和最后一个k的位置，区间长度=尾地址-首地址+1；

#include<bits/stdc++.h>
using namespace std;
int ans;
int a[10000010];

//返回第一个p的位置，如不存在p，返回0  
int bs1(int l,int r,int p){
    ans=0;  //答案初始化为0 
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]>=p){
            ans=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    if(a[ans]!=p) ans=0;  //判断答案是否为p 
    return ans;
}

//返回第一个p的位置，如不存在p，返回0 
int bs2(int l,int r,int p){
    ans=0;  //答案初始化为0 
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]<=p){
            ans=mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    if(a[ans]!=p) ans=0;  //判断答案是否为p 
    return ans;
}

int main(){
    int n,m,k;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        cin>>k;
        if(bs1(1,n,k))   //返回值为真，k存在 
            cout<<bs2(1,n,k)-bs1(1,n,k)+1<<" ";
        else cout<<0<<" ";
    }
    return 0;
}

写法三：二分查找，找到k的位置，从找到的位置分别向前、向后搜索

ps：代码来自王嘉宇同学

#include<bits/stdc++.h>
using namespace std;
int a[10000005];
int main() {
    int n,m,sum=0,k;
    cin>>n>>m;
    int l=1,r=n;
    int ans=0;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
    }
    for(int j=1; j<=m; j++) {
        cin>>k;
        l=1;  r=n;   sum=0;  //初始化左边界、右边界、答案 
        
        //二分查找，找到k的位置 
        while(l<=r) {
            int mid=(l+r)/2;
            if(a[mid]==k) {
                ans=mid;
                break;
            } else if(a[mid]>k) {
                r=mid-1;
            } else
                l=mid+1;
        }
        if(a[ans]==k) {  //k存在
            //从找到的位置向后搜索，不等于k时跳出循环 
            for(int w=ans; w<=n; w++) {
                if(a[w]==k) {
                    sum++;
                } else {
                    break;
                }
            }
            //从找到的位置向前搜索，不等于k时跳出循环 
            for(int v=ans; v>=1; v--) {
                if(a[v]==k) {
                    sum++;
                } else {
                    break;
                }
            }
            sum-=1;
        }
        cout<<sum<<" ";
    }
    return 0;
}