输入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

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    int *R;
    int length;
} SSTable;

void Init(SSTable* ST)
{
    ST->length = 0;
    ST->R = (int*)malloc(sizeof(int)*100);
}

int Search_Bin(SSTable ST, int x, int* m)
{
    int low = 1, high = ST.length, mid;
    while(low <= high)
    {
        (*m)++;
        mid = (low+high)/2;
        if(x == ST.R[mid])
        {
            return mid;
        }
        else if(x < ST.R[mid])
        {
            high = mid-1;
        }
        else if(x > ST.R[mid])
        {
            low = mid + 1;
        }
    }
    return 0;
}


int main()
{
    SSTable ST;
    Init(&ST);
    //输入长度
    scanf("%d",&ST.length);
    //输入值
    for(int i = 1; i <= ST.length; i++)
    {
        scanf("%d",&ST.R[i]);
    }
    //输入查找的数
    int x, m = 0;
    scanf("%d",&x);
    printf("%d\n",Search_Bin(ST, x, &m)-1);
    printf("%d\n", m);


    return 0;
}