1909 - 改写二分搜索算法

4
5
1 3 5 6 8

0
1
2

Solution C

/*设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，
返回小于x的最大元素的位置 i 和大于x的最小元素位置 j。当搜索元素在数组中时，i 和 j 相同，
均为x在数组中的位置。*/
#include<stdio.h>
int main()
{
	void BFind(int *,int ,int,int);
	int x,n,i;
	scanf("%d%d",&x,&n);
	int t[n];
	for(i=0;i<n;i++)
        scanf("%d",&t[i]);
	BFind(t,0,n,x);
	return 0;
}
void BFind(int *t,int m,int n,int x)
{
	while(m<n)
	{
		if(x>t[(m+n)/2])
			m=(m+n)/2+1;
        if(x<t[(m+n)/2])
            n=(m+n)/2-1;
        if(x==t[(m+n)/2])
            {
                printf("1\n%d\n",(m+n)/2);
                return ;
            }
	}
	printf("0\n%d\n%d\n",m,m+1);
	return ;
}

Solution C++

#include<iostream>
using namespace std;
int B(int a[],int x,int n,int &i,int &j)
	{    
		int left=0;
	    int right=n-1;
		while(left<=right)
		{
			int middle=(left+right)/2;
				if(x==a[middle])
					return middle;
				if(x>a[middle])
				left=middle+1;
				else
				right=middle-1;
	
		}
		i=right;
		j=left;
		return -2;
	}
int main()
	{
	
        int x,n;
		int i=0;
		int j=0;
		cin>>x>>n;
		int a[1000];
		for(i=0;i<n;i++)
		cin>>a[i];
		int C=B(a,x,n,i,j);
	if(C>=0)
		cout<<1<<"\n"<<C<<endl;
	else
		cout<<0<<"\n"<<i<<"\n"<<j<<"\n";
}