Бинарный поиск элемента

Question

Требуется реализовать бинарный поиск элемента с заданным значением в отсортированном массиве. В первой строке записано одно целое число ? — размер отсортированного массива (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);
}
}

Answer 1

В условии вроде говорится о сортированном массиве, так что сортировать его, вероятно, не нужно. Если всё-таки входные данные не сортированы, то InsertionSort - неудачный выбор для размера массива 10^5, требуется использовать более быструю сортировку - qsort() есть в стандартной библиотеке.

Кроме того, если таких элементов много, то в качестве ответа ?? следует выбрать самый большой индекс. подразумевает использование модификации бинарного поиска, возвращающей самый правый элемент - wiki

function binary_search_rightmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] > T:
            R := m
        else:
            L := m + 1
    return R - 1

Answer 2

Откровенно говоря, думал, что потребуется что-то типа оптимизации по запросам - ну, смотреть на возможный диапазон исходя из предыдущего решения, но все оказалось лишним - повторения обычного простого бинарного поиска оказалось достаточно...

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

int a[100000];

int* upper_bound(int* first, int* last, int value)
{
    int * it;
    int count = last-first, step;
    while (count > 0)
    {
        it = first; 
        step = count / 2;
        it += step;
        if (!(value < *it))
        {
            first = ++it;
            count -= step + 1;
        } 
        else
            count = step;
    }
    return first;
}

int main()
{
    int N, Q, R = 0, X;
    scanf("%d",&N);
    for(int i = 0; i < N; ++i) scanf("%d",a+i);
    scanf("%d",&Q);
    for(int i = 0; i < Q; ++i)
    {
        scanf("%d",&X);
        X += R;
        int * f = upper_bound(a,a+N,X);
        if (*(f-1) != X) R = -1; else R = f-1-a;
        printf("%d\n",R);
    }
}

БЛОГ НА HUSL

Бинарный поиск элемента

Ответы (2 шт):