【问题描述】

设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置i和大于x的最大元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

【输入形式】

输入有两行：

第一行是n值和x值；

第二行是n个不相同的整数组成的非降序序列，每个整数之间以空格分隔。

【输出形式】

第一行输出小于x的最大元素的最大下标i和大于x的最小元素的最小下标j。

当搜索元素在数组中时，i和j相同。

提示：若x小于全部数值，则输出：-1 0 ;若x大于全部数值，则输出：n-1 n

第二行若找到返回下标,否则返回-1

【样例输入】

6 5
2 4 6 8 10 12

【样例输出】

1 2
-1

c++代码

#include<iostream>
using namespace std;
bool BinarySearch(int *a,int n,int x,int& i,int& j){
    int left=0;
    int right=n-1;
    while(left<=right){
        int mid=(left+right)/2;
        if(x==a[mid]){
            i=j=mid;
            return true;
        }
        if(x>a[mid])
            left=mid+1;
        else
            right=mid-1;
    }
    i=right;
    j=left;
    return false;
}

int SearchTag(int *a,int n,int x){
    int left=0;
    int right=n-1;
    while(left<=right){
        int mid=(left+right)/2;
        if(x==a[mid]) return mid;
        if(x>a[mid])
            left=mid+1;
        else
            right=mid-1;
    }
    return -1;
}

int main(){
    int n,i,j,a[1000],x;
    cin>>n>>x;
    for(i=0;i<n;i++)
		cin>>a[i];
    BinarySearch(a,n,x,i,j);
    cout<<i<<' '<<j<<endl;
    cout<<SearchTag(a,n,x)<<endl;
	return 0;
}