急求完善两道简单的算法分析题

Question

1、设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置I和大于x的最大元素位置j。当搜索元素在数组中时，I和j相同，均为x在数组中的位置。
2、设有n个不同的整数排好序后存放于t[0:n-1]中，若存在一个下标I，0≤i＜n，使得t[i]=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O（logn）。
三、实验提示
1、用I，j做参数，且采用传递引用或指针的形式带回值。
bool BinarySearch(int a[],int n,int x,int& i,int& j)
{
int left=0;
int ri ght=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;
}
2
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])
right=mid-1;
else
left=mid+1;
}
return -1;
}
核心的算法已经有了，谁能帮忙看看对不对，如果对的话请能帮忙完善一下，就是可以在dos窗口接受用户输入值，然后输出结果。几年没用到C和C++了，现在临时要用，实在没时间在去看之类的书，希望哪位好心能帮一下忙，十分感谢，
非常感谢，能否将第二道题完善呢 不用用户输入也行 直接定义一个数组来测试也可以 但能输出结果 不胜感激

Answer 1

第一题的题目有误吧
返回小于x的最大元素的位置I和大于x的最大元素位置j
应该是
返回小于x的最大元素的位置I和大于x的最小元素位置j

算法有点问题

第二题的算法不对

两道题目都是要假设 a[0:n-1]是一个已排好序的数组 并且是严格单调递增的。

// 二分查找.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <stdio.h>

#define N 10

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

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

int _tmain(int argc, _TCHAR* argv[])
{
int a[N];
printf("请输入%d个由小到大排列的整数\n以空格隔开，以回车结束\n",N);

int k;
for(k=0;k<N;k++)
scanf("%d",a+k);
printf("你的输入如下：\n");
for(k=0;k<N;k++)
printf("%d\t",k);
//printf("\n");
for(k=0;k<N;k++)
printf("%d\t",a[k]);
printf("\n");

if((k=SearchTag(a,N))!=-1)
printf("第%d个数字满足a[%d]=%d\n",k,k,k);
else
printf("没有找到任何一个数字满足a[i]=i\n");

int i,j;
int x;
printf("请输入你想要查找的数字\n");
scanf("%d",&x);
if(BinarySearch(a,N,x,i,j))
printf("找到了：i和j均在%d\n",j);
else
printf("没找到：j=%d\ti=%d\n",j,i);

getchar();
getchar();
return 0;
}