求解C++语言编写 急急

7-1 二分查找（20 分）
输入n值(1<=n<=1000)、n个整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。
输入格式:

输入共三行： 第一行是n值； 第二行是n个整数； 第三行是x值。
输出格式:

输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。

输入样例:

4
1 2 3 4
1
输出样例:

0
2

 #include <iostream>

using namespace std;
void test(int a[],int n,int v);
int main()
{
    int n,i=0,v;
    int a[1000];
    cin>>n;
    while(i!=n)
    {
        cin>>a[i++];
    }
    cin>>v;
    test(a,n,v);
    return 0;
}
void test(int a[],int n,int v)
{
    int i = 0;
    int index = n;
    while(index!=0){
            index/=2;
        if(a[index]==v){
            cout<<index<<"\n"<<i<<"\n";
            return;
        }else
        {
           i++;
        }
    }
    cout<<-1<<"\n"<<i<<"\n";
}

要注意一点，用二分查找的那个数组必须是有序的。

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX = 1000 + 10;

typedef struct {
    int val, id; //分别为值和下标位置
}Point;

int n;
Point a[MAX];
int num;

//将a[ ]按值的大小从小到大排序
bool cmp(Point x, Point y)
{
    if (x.val == y.val)
        return x.id < y.id;
    return x.val < y.val;
}

int bin_search(int x)
{
    int l = 0;
    int r = n;
    while (r - l >= 1)
    {
        int i = (l + r) >> 1;
        if (a[i].val == x)
            return a[i].id;
        else if (a[i].val < x)
            l = i + 1;
        else
            r = i;
        num++;
    }
    return -1;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].val;
        a[i].id = i;
    }
    sort(a, a + n, cmp);
    int x;
    cin >> x;
    num = 0;
    int pos = bin_search(x);
    cout << pos << endl;
    cout << num << endl;
    return 0;
}

我个人觉得题目描述有些问题，如果存在相同的数该返回哪个数的下标？

#include

using namespace std;
void test(int a[],int n,int v);
int main()
{
int n,i=0,v;
int a[1000];
cin>>n;
while(i!=n)
{
cin>>a[i++];
}
cin>>v;
test(a,n,v);
return 0;
}
void test(int a[],int n,int v)
{
int i = 0;
int index = n;
while(index!=0){
index/=2;
if(a[index]==v){
cout<<index<<"\n"<<i<<"\n";
return;
}else
{
i++;
}
}
cout<<-1<<"\n"<<i<<"\n";
}

抱歉，上面给的代码有误，这是改正后的代码

 #include <iostream>

using namespace std;
void test(int a[],int n,int v);
int main()
{
    int n,i=0,v;
    int a[1000];
    cin>>n;
    while(i!=n)
    {
        cin>>a[i++];
    }
    cin>>v;
    test(a,n,v);
    return 0;
}
void test(int a[],int n,int v)
{
    int i = 0;
    int index;
    int low = 0;
    int high = n-1;
    while(low<=high){
        index = (low + high)/2;
        if(low == n-2 && high == n-1) index = n-1;//边界处理
        if(a[index]==v){
            i++;
            cout<<index<<"\n"<<i<<"\n";
            return;
        }else if(a[index]>v)
        {
            i++;
            if(index == 0) break;//如果a[0]大于v，那么就不在范围内
            high = index;

        }else
        {
            i++;
            if(index == n-1) break;//如果a[n-1]小于v，那么就不在范围内
            low = index;
        }
    }
    cout<<-1<<"\n"<<i<<"\n";
}