二进制元素搜索

需要对已排序数组中具有给定值的元素进行二进制搜索。第一行包含一个整数 𝑁 — 排序数组的大小 (1 <= 𝑁 <= 10^5)。接下来，写入数组𝐴𝑖（整数的𝑁，|𝐴𝑖| <= 10^9）的元素。然后写入一个整数 𝑄 — 需要处理的请求数 (1 <= 𝑄 <= 10^5)。剩下的 𝑄 行包含定义搜索查询的整数 𝑋𝑗。每个请求必须按如下方式处理。首先，您需要将前面查询的答案𝑅𝑗−1 添加到文件中写入的数字𝑋𝑗，得到𝑌𝑗 = 𝑋𝑗 + 𝑅𝑗−1。然后你需要在数组𝐴中找到一个等于𝑌𝑗的元素：它的索引将是这个查询的答案𝑅𝑗。如果有很多这样的元素，那么应该选择最大的索引作为答案𝑅𝑗。如果没有这样的元素，那么答案𝑅𝑗是-1。数组元素的索引从 0 到𝑁 − 1。第一个查询没有先前的答案，所以我们把 𝑌0 = 𝑋0。 告诉我如何改进程序：

#include <stdio.h>
#include <malloc.h>
#include <conio.h>

int binarysearch(int a, int mass[], int n);
void InsertionSort(int n, int mass[]);

int main()
{
    int N, a;
    printf("Input N: ");
    scanf_s("%d", &N);
    int* mass;
    mass = (int *)malloc(N * sizeof(int));
    printf("Input the array elements:\n");
    for (int i = 0; i < N; i++)
        scanf_s("%d", &mass[i]);
    InsertionSort(N, mass);
    printf("Sorted array:\n");
    for (int i = 0; i < N; i++)
        printf("%d ", mass[i]);
    printf("\n");
    printf("Input variable 'a' for search: ");
    scanf_s("%d", &a);
    int k;
    k = binarysearch(a, mass, N);
    if (k != -1)
    {
        printf("The index of the element is %d\n", k);
    }
    else
        printf("The element isn't found!\n");
    free(mass);
    _getch();
    return 0;
}

int binarysearch(int a, int mass[], int n)
{
    int low, high, middle;
    low = 0;
    high = n - 1;
    while (low <= high)
    {
        middle = (low + high) / 2;
        if (a < mass[middle])
            high = middle - 1;
        else if (a > mass[middle])
            low = middle + 1;
        else 
            return middle;
    }
    return -1;
}

 
void InsertionSort(int n, int mass[])
{
    int newElement, location;

    for (int i = 1; i < n; i++)
    {
        newElement = mass[i];
        location = i - 1;
        while (location >= 0 && mass[location] > newElement)
        {
            mass[location + 1] = mass[location];
            location = location - 1;
        }
        mass[location + 1] = newElement;
    }
}

UPD： 我能够搞砸一些事情，但测试系统说程序没有通过所有测试。怎么了？？？

#include<stdio.h>
int a[1000000];
int main()
{
int N,Q,c;
scanf("%d",&N);
if (N!=0){
int x,y=0,z=0;
for(int i=0;i<N;i++)
{
scanf("%d",&c);
a[c]=i;
}
scanf("%d",&Q);
for(int i=0;i<Q;i++)
{
scanf("%d",&x);
y+=x;
int j=0;
int flag=0;
z=a[y];
if (z!=0)
{
flag=1;
}
y=z;
if (flag==0)
y=-1;
printf("%d\n",y);
j++;
}
return(0);
}
}