Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.97/34: Рейтинг темы: голосов - 34, средняя оценка - 4.97
3 / 3 / 0
Регистрация: 30.09.2020
Сообщений: 85

Поиск ближайшего элемента в отсортированном массиве

18.11.2020, 16:36. Показов 7735. Ответов 27

Студворк — интернет-сервис помощи студентам
Требуется реализовать поиск в отсортированном массиве элемента, ближайшего к заданному значению. В первой строке записано одно целое число N - размер отсортированного массива(1<=N<=10^5). Далее записаны элементы массива A[i](N целых чисел, |A[i]|<=10^9). Затем записано целое число Q - количество запросов, которые нужно обработать(1<=Q<=10^5). В остальных Q строках записаны целые числа Y[j], определяющие запросы на поиск. Запросы нужно обрабатывать следующим образом. Для каждого числа Y[j] нужно найти в массиве А такой элемент, чтобы разность между ним и Y[j] была минимальной. Нужно вывести два целых числа через пробел: индекс найденного элемента и полученное минимальное расстояние. Элементы массива нумеруются от 0 до (N-1). Если ближайших элементов несколько, разрешается выводить индекс любого из них. В данной задаче ответ каждого запроса нужно находить независимо от всех остальных запросов за время O(log N) в худшем случае.
Помогите доработать программу, пожалуйста. Тут уже тупиковая ситуация
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stdio.h>
int main(){
    int N;
    scanf("%d\n", &N);
    int A[10001];
    int Y[10001];
    int index_first = 0;
    int index_last = N-1;
    for (int i=0; i<N; i++){
        scanf("%d ", &A[i]);
    }
    int Q;
    scanf("%d\n", &Q);
    for(int j=0; j<Q; j++){
        scanf("%d\n", &Y[j]);
    }
    int index_middl = index_last / 2;
for(int j=0; j<Q; j++){
    while (index_first < index_last) {
        if (Y[j] < A[index_middl]) {
            index_last = index_middl;
        } 
        else {
            index_first = index_middl;
         }
        index_middl = index_last / 2;
        if (element == array[index_middl]) 
            break;
    }
}
}
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
18.11.2020, 16:36
Ответы с готовыми решениями:

Нахождение элемента, ближайшего к среднему в массиве
нужно найти элемент, ближайший к среднему в массиве, помогите найти ошибку #include &lt;conio.h&gt; #include &lt;math.h&gt; ...

Поиск элемента в не отсортированном массиве
Здравствуйте. Необходимо написать программу, которая генерирует массив с помощью RND, а затем найти индекс елемента, который пользователь...

Поиск элемента в отсортированном массиве
какое минимальное колличество итераций при поиске элемента в отсортированом массиве по возрастанию из 100 элементов?

27
Заблокирован
18.11.2020, 18:34
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от A_Hatake Посмотреть сообщение
Помогите написать, что получится в main, там по сути только ввод.
что помочь-то? ввод чисел в массив написать? Так у тебя же есть все это уже в коде твоем.

Добавлено через 5 секунд
Цитата Сообщение от A_Hatake Посмотреть сообщение
Помогите написать, что получится в main, там по сути только ввод.
что помочь-то? ввод чисел в массив написать? Так у тебя же есть все это уже в коде твоем.
0
3 / 3 / 0
Регистрация: 30.09.2020
Сообщений: 85
18.11.2020, 18:51  [ТС]
sodda, да. Честно говоря, с этим и помочь. Уже запуталась, пока писала функцию. Теперь же не с нуля уже писать?
0
Заблокирован
18.11.2020, 18:58
A_Hatake, так я тебе сто раз уже все написал.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
 
int main(){
    int N;
    int magic_number = 0;
    int lower_index = 0;
    int upper_index = 0;
    int m[100];
    printf("Укажите длинну массива: ");
    scanf("%d", &N);
    
    
   
    for (int i=0; i<N; i++) {
        printf("m[%d] = ", i);
        scanf("%d", &m[i]);
    }
    
    
    printf("Введите искомое число: ");
    scanf("%d", &magic_number);
    
    return 0;
    
}
0
3 / 3 / 0
Регистрация: 30.09.2020
Сообщений: 85
18.11.2020, 19:01  [ТС]
sodda, да это же не то совершенно, и к функции моей не подходит
0
Заблокирован
18.11.2020, 19:05
A_Hatake, что значит не то? я у тебя спросил ты ответила да, надо заполнить массив числами.
не подходит - пиши сама. я и так с тобой много времени потратил.
0
3 / 3 / 0
Регистрация: 30.09.2020
Сообщений: 85
18.11.2020, 19:09  [ТС]
Во-первых, вы не то спросили, и я попросила помощи с написанием ввода, подходящим к моей функции. Если вы продолжали все это время обсуждение со мной, значит вам была интересна тема обсуждения, а нет - не тратили бы время.
Во-вторых - невежливо обращаться к незнакомому человеку на "ты", неважно какого собеседник возраста.
Спасибо хоть и на том, что потратили на меня много времени.
0
Заблокирован
18.11.2020, 19:22
Цитата Сообщение от A_Hatake Посмотреть сообщение
я попросила помощи с написанием ввода, подходящим к моей функции.
один вопрос - одна тема. не забывайте правила форума.
это во-первых.
Цитата Сообщение от A_Hatake Посмотреть сообщение
невежливо обращаться к незнакомому человеку на "ты"
кто такое сказал?
глупости.

В-третьих нужно чётко выражать свои мысли.
Я в самом начал спросил - "Нужно найти ближайший число?".
Ты говоришь - "Да".
Я тебе пишу код. Ты говоришь - это то, но не совсем то, потому что нужно не совсем найти ближайшее число.
0
3 / 3 / 0
Регистрация: 30.09.2020
Сообщений: 85
18.11.2020, 19:34  [ТС]
sodda, тут вы уже сами додумываете И число, действительно, нужно найти ближайшее. Вот только ввод-вывод данных должен быть согласован с условием, которое, кстати, прикреплено с самого начала. Так что надо было просто помочь с вводом-выводом данных к моей функции... Короче говоря, я вас не понимаю, вы меня не можете понять.
Спасибо за потраченное время.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
18.11.2020, 19:34

Поиск нужного элемента в отсортированном массиве
Здраствуйте. Решаю задачу 2 день, неполучается. Подумал сюда обратиться. В общем задача такая. Есть отсортированый массив integer (int a),...

Поиск индекса заданного элемента в отсортированном массиве
1. Заполнить статический массив значениями 90, 76, 54, 23, 56, 12, 48. Результат в виде таблицы значений массива вывести на консоль. ...

Поиск элемента в отсортированном массиве методом бинарного дерева
Как найти элемент в отсортированном массиве, методом бинарного дерева, не могу найти этот метод..есть только бинарный поиск, это одно и...

В отсортированном массиве произвести бинарный поиск индекса элемента со значением K
Дан линейный целочисленный массив из N элементов. Отсортировать элементы массива в порядке не убывания их значений (метод сортировки...

В отсортированном одномерном массиве выполнить поиск заданного элемента последовательным методом
Знаю,что тут есть похожая очень тема, но не могу справиться который день...так что прошу помощи:wall: В отсортированном одномерном массиве...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
28
Ответ Создать тему
Новые блоги и статьи
Про "Windows must die!"
kumehtar 04.11.2026
Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .
Красочные поля с номером страницы svg+background-image
russiannick 04.11.2026
Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .
Вступаем в новую фазу генерации favicons, векторную.
russiannick 02.11.2026
Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .
Генератор паролей (вариант №4)
Maks 01.11.2026
После публикации 3-го варианта генератора паролей, разослал его своим коллегам (с целью оценки), в итоге были получены следующие рекомендации: 1. Вернуть возможность использования знаков | 1 l I;. . .
Генератор паролей (вариант №3)
Maks 30.10.2026
Финальная версия генератора паролей 1С. Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты:. . .
Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени)
zorxor 30.10.2026
Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию? Фраза «Любая достаточно развитая технология неотличима от магии». . .
За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ)
zorxor 30.10.2026
Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль? Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .
Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени)
zorxor 30.10.2026
Как убивали Suno. Хронология. «Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru