Ошибка: приближенный бинарный поиск

@RaphisGunn · Регистрация: 25.01.2024

Author24 — интернет-сервис помощи студентам

Добрый день! Код не проходит один тест. Не понимаю, в чём ошибка. Помогите, пожалуйста, найти.

Условие задачи:
Реализуйте алгоритм приближенного бинарного поиска.

Входные данные:
В первой строке входных данных содержатся числа N и K (0<N,K<100001). Во второй строке задаются N чисел первого массива, отсортированного по неубыванию, а в третьей строке – K чисел второго массива. Каждое число в обоих массивах по модулю не превосходит 2⋅ $https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{9}$ .

Выходные данные:
Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному. Если таких несколько, выведите меньшее из них.

C++

#include <iostream>
#include <cmath>
using namespace std;
 
int MostClose(int Mass[], int N, int a) {
    int L = 0, R = N;
    int c;
    
    while (L < R - 1)
    {
        c = (L + R) / 2;
        if (a < Mass[c])
        {
            R = c;
        }
        else
        {
            L = c;
        }
    }
    
    int mostclose;
    if (Mass[L] == a)
    {
        mostclose = Mass[L];
    }
    else 
    {
        if (abs(Mass[L] - a) <= abs(Mass[R] - a))
        {
            mostclose = Mass[L];
        }
        else
        {
            mostclose = Mass[R];
        }
    }
    
    return mostclose;
}
 
int main() 
{
    int N, K;
    cin >> N >> K;
 
    int i;
    
    int MainMass[N];
    for (i = 0; i < N; i++)
    {
        cin >> MainMass[i];
    }
    
    int SideMass[K];
    for (i = 0; i < K; i++) 
    {
        cin >> SideMass[i];
    }
    
    for (i = 0; i < K; i++) 
    {
        cout << MostClose(MainMass, N, SideMass[i]) << endl;
    }
    
    return 0;
}

@TheCalligrapher · 25.01.2024, 09:58

Сообщение от RaphisGunn

Не понимаю, в чём ошибка.

Ну так R изначально не является правльным индексом для массива:

C++

6	int L = 0, R = N;

Если в процессе работы цикла поиска значение R не менялось вообще, а менялось только L, то R так и останется равно N.

А тогда вот это

C++

29	if (abs(Mass[L] - a) <= abs(Mass[R] - a))

приведет к неопределенному поведению: выход за пределы массива.

Сообщение от RaphisGunn

Код не проходит один тест.

Тест как раз специально составлен в расчете на то, что вы сделаете эту ошибку.

Сообщение от RaphisGunn

C++

int N, K;
...
int MainMass[N];
...
int SideMass[K];

В С++ такого вообще не разрешается.

nikulin_artyom1 · 25.01.2024, 11:07

Как-то так.

C++

#include <iostream>
#include <cmath>
using namespace std;
 
int MostClose(int Mass[], int N, int a) {
    int L = 0, R = N - 1;
    int c;
    
    while (L < R)
    {
        c = (L + R) / 2;
        if (a <= Mass[c])
        {
            R = c;
        }
        else
        {
            L = c + 1;
        }
    }
    
    int mostclose;
    if (L > 0 && abs(Mass[L] - a) >= abs(Mass[L - 1] - a))
    {
        mostclose = Mass[L - 1];
    }
    else 
    {
        mostclose = Mass[L];
    }
    
    return mostclose;
}
 
int main() 
{
    int N, K;
    cin >> N >> K;
 
    int i;
    
    int MainMass[N];
    for (i = 0; i < N; i++)
    {
        cin >> MainMass[i];
    }
    
    int SideMass[K];
    for (i = 0; i < K; i++) 
    {
        cin >> SideMass[i];
    }
    
    for (i = 0; i < K; i++) 
    {
        cout << MostClose(MainMass, N, SideMass[i]) << endl;
    }
    return 0;
}

Новые блоги и статьи
Как написать микросервис с нуля на C# InfoMaster 14.01.2025 В современном мире разработки программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот архитектурный подход предполагает. . .	Как создать интернет-магазин на PHP и JavaScript InfoMaster 14.01.2025 В современном мире электронная коммерция стала неотъемлемой частью бизнеса. Создание собственного интернет-магазина открывает широкие возможности для предпринимателей, позволяя достичь большей. . .	Как написать Тетрис на Ассемблере InfoMaster 14.01.2025 Тетрис – одна из самых узнаваемых и популярных компьютерных игр, созданная в 1984 году советским программистом Алексеем Пажитновым. За прошедшие десятилетия она завоевала симпатии миллионы людей по. . .	Как создать игру "Танчики" на Unity3d и C# InfoMaster 14.01.2025 Разработка игр – это увлекательный процесс, сочетающий в себе творчество и технические навыки. В этой статье мы рассмотрим создание классической игры "Танчики" с использованием Unity3D и языка. . .	Организую платный онлайн микро-курс по доработке Android-клиента Telegram _Ivana 14.01.2025 Официальная версия и распространенные форки не полностью устраивают? Сделай свою кастомную версию клиента! 4 занятия по 2 часа (2 недели пн, ср 19:00-21:00 по Москве). Первое вводное занятие. . .	Как создать приложение для фитнеса для iOS/iPhone на Kotlin InfoMaster 14.01.2025 Создание собственного фитнес-приложения — это не только захватывающий, но и полезный процесс, ведь оно может стать вашим верным помощником на пути к здоровому и активному образу жизни. В современных. . .
Как создать приложение магазина для iOS/iPhone на Swift InfoMaster 14.01.2025 Введение в разработку iOS-приложений Разработка приложений для iPhone и других устройств на базе iOS открывает огромные возможности для создания инновационных мобильных решений. В данной статье мы. . .	Это работает. Скорость асинхронной логики велика. Вопрос видимо останется в стабильности. Плата - огонь! Hrethgir 13.01.2025 По прошлому проекту в Logisim Evolution https:/ / www. cyberforum. ru/ blogs/ 223907/ blog8781. html прилагаю файл архива проекта Gowin Eda и снимок. Восьмибитный счётчик из сумматора+ генератор сигнала. . .	UserScript для подсветки кнопок языков программирования в зависимости от текущего раздела volvo 13.01.2025 В результате работы этого скрипта подсвечиваются нужные кнопки не только в форме быстрого ответа, но и при редактировании сообщения: / / ==UserScript== / / @name CF_DefaultLangSelect / / . . .	Введение в модели и алгоритмы машинного обучения InfoMaster 12.01.2025 Машинное обучение представляет собой одну из наиболее динамично развивающихся областей искусственного интеллекта, которая фокусируется на разработке алгоритмов и методов, позволяющих компьютерам. . .	Как на Python создать нейросеть для решения задач InfoMaster 12.01.2025 В контексте стремительного развития современных технологий особое внимание уделяется таким инструментам, как нейросети. Эти структуры, вдохновленные биологическими нейронными сетями, используются для. . .	Как создать нейросеть для генерации картинок на Python InfoMaster 12.01.2025 Генерация изображений с помощью искусственных нейронных сетей стала одним из наиболее захватывающих направлений в области компьютерного зрения и машинного обучения. В этой статье мы рассмотрим. . .

	25.01.2024, 11:07

Ошибка: приближенный бинарный поиск

Решение