1 / 1 / 0
Регистрация: 03.04.2014
Сообщений: 16
1

Двоичный поиск в упорядоченном массиве

07.04.2014, 12:09. Показов 2089. Ответов 3
Метки нет (Все метки)

Дан упорядоченный по неубыванию целочисленный массив и набор чисел ki. Требуется для каждого числа ki найти позиции первого и последнего его вхождения в массив.

Исходные данные
Вначале вводится число N от 1 до 1000000 - количество элементов в массиве. После этого на ввод поступает N целых чисел в диапазоне от 0 до 1 миллиарда в неубывающем порядке - элементы масива. Затем указывается количество запросов M (от 1 до 100000). Затем вводится M чисел ki. Все числа отделяются друг от друга пробелами и/или переводами строк.

Результат
Для каждого запроса выведите два числа - первую и последнюю позиции числа ki в массиве. Если такое число в массиве не встречается, выведите -1

Подскажите пожалуйста как это реализовать.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.04.2014, 12:09
Ответы с готовыми решениями:

Бинарный (двоичный) поиск по алфавиту в упорядоченном массиве структур
Приветствую товарищей-программистов! Есть массив структур StructWords massiv. struct...

Бинарный поиск в упорядоченном массиве
Задали реализовать бинарный поиск в упорядоченном массиве.Уже пол дня творю,3 листа исписал и...

Бинарный поиск числа в упорядоченном массиве
В упорядоченном массиве надо найти число. Программа должна выполняться с рекурсией

Бинарный поиск в упорядоченном по возрастанию массиве
Напишите программу, которая, используя метод бинарного поиска, выполняет поиск в упорядоченном по...

3
Заблокирован
07.04.2014, 12:37 2
std::equal_range
0
1 / 1 / 0
Регистрация: 03.04.2014
Сообщений: 16
08.04.2014, 13:08  [ТС] 3
newbie666, мне это ничего не говорит, надо конкретные методы
0
Заблокирован
08.04.2014, 21:57 4
Цитата Сообщение от alexlight91 Посмотреть сообщение
мне это ничего не говорит
Это твоя головная боль, если есть чему там болеть конечно, если тебе это ни о чём не говорит.
Цитата Сообщение от alexlight91 Посмотреть сообщение
надо конкретные методы
я тебе сказал что использовать, действуй. Хотя куда там Ладно - скопирую тебе пример с хорошего сайта, как применить его себе - уж будь любезен, сам додумывай:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// lower_bound/upper_bound example
#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort
#include <vector>       // std::vector
 
int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  std::vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20
 
  std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30
 
  std::vector<int>::iterator low,up;
  low=std::lower_bound (v.begin(), v.end(), 20); //          ^
  up= std::upper_bound (v.begin(), v.end(), 20); //                   ^
 
  std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
  std::cout << "upper_bound at position " << (up - v.begin()) << '\n';
 
  return 0;
}
Output:
lower_bound at position 3
upper_bound at position 6
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.04.2014, 21:57
Помогаю со студенческими работами здесь

Поиск элемента, меньшего заданного, в упорядоченном массиве
Добрый день. Мне необходимо найти в массиве первый элемент, который меньше заданного, и, очень...

Поиск заданного элемента в упорядоченном по возрастанию массиве целых чисел
Осуществить поиск заданного элемента в упорядоченном по возрастанию (по убыванию) массиве целых...

Осуществить поиск данного числа в упорядоченном по возрастанию массиве методом бинарного поиска
Всем привет. Не могу понять как сделать, чтобы программа выводила в консоль надпись, что нету...

Сортировка и двоичный поиск в массиве.
Помогите чайнику изменить следующий код: // F_08_L_2.cpp: определяет точку входа для консольного...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru