Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.71
TyLinka
32 / 32 / 11
Регистрация: 02.02.2012
Сообщений: 177
#1

Левый и правый двоичный поиск - C++

29.06.2013, 10:51. Просмотров 2686. Ответов 1
Метки нет (Все метки)

Помогите, пожалуйста, не проходит 1 тест, не понимаю из-за чего

Дано два списка чисел, числа в первом списке упорядочены по неубыванию. Для каждого числа из второго списка определите номер первого и последнего появления этого числа в первом списке.

Формат входных данных
В первой строке входных данных записано два числа N и M (1NM20000). Во второй строке записано N упорядоченных по неубыванию целых чисел — элементы первого списка. В третьей строке записаны M целых неотрицательных чисел - элементы второго списка. Все числа в списках - целые 32-битные знаковые.

Программа должна вывести M строчек. Для каждого числа из второго списка нужно вывести номер его первого и последнего вхождения в первый список. Нумерация начинается с единицы. Если число не входит в первый список, нужно вывести одно число 0.

Примеры
входные данные10 5
1 1 3 3 5 7 9 18 18 57
57 3 9 1 179
выходные данные
10 10
3 4
7 7
1 2
0

Вот моё решение:
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
32
33
34
35
36
37
38
39
40
#include <iostream>
 
using namespace std;
 
int main()
{
    long n, k, m;
    cin >> n >> k;
    long *a = new long[n];
    long *b = new long[k];  
 
    for (long i = 0; i < n; i++)
        cin >> a[i];
 
    for (long i = 0; i < k; i++)
        cin >> b[i];
 
    for (long i = 0; i < k; i++)
    {
        int l = 0, r = n - 1;
        while (l < r)
        {
            m = (l + r) / 2;
            if (a[m] < b[i]) l = m + 1;
            else r = m;
        }
        if (a[r] == b[i])
        {
            cout << ++r << " ";
            while (a[r] == b[i])
                r++;
            cout << r << endl;
        }
        else cout << 0 << endl;
    }
 
    delete [] a;
    delete [] b;
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.06.2013, 10:51
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Левый и правый двоичный поиск (C++):

Совершить в бинарном дереве обход Правый - Корень - Левый - C++
Нужно совершить обход Правый корень левый в бинарном дереве. #include &quot;stdafx.h&quot; #include &quot;stdlib.h&quot; #include &quot;conio.h&quot; #include...

Поменять местами левый и правый байты целого аргумента - C++
разработайте макрос swab(х) который меняет местами левый и правый байты целого аргумента х .Спасибо!

Найти в строке way левый слеш и заменить его на правый - C++
Есть код, нужно найти в строке way левый слеш и заменить его на правый) void main() { string way(&quot;asdas\sdasd\dsa&quot;); int pos =...

Найти левый и правый крайние отрицательные элементы в массиве из 20 элементов - C++
Помогите решить проблему. Есть задание &quot;Создать целочисленный массив из 20 элементов.Заполнить его числами в диапазоне от -13 до 13. ...

Написать программу которая при нажатии клавиш:правый Shift+ правый Alt блокировала бы клавишу 9 на клавиатуре. - C++
Добрый день Необходимо написать программу которая при нажатии клавиш:правый Shift+ правый Alt блокировалась бы клавиша 9 на клавиатуре.

двоичный поиск - C++
Подскажите, пожалуйста, в вопросе: Какое дополнительное требование к массиву может быть применено при двоичном поиске, что бы определить...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
el_gato_de_Ch
35 / 35 / 1
Регистрация: 28.04.2013
Сообщений: 110
29.06.2013, 16:54 #2
lower_bound()
и
upper_bound()

Вам в помощь. Один ищет первое вхождение, второй последнее вхождение элемента в контейнер
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.06.2013, 16:54
Привет! Вот еще темы с ответами:

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

Двоичный поиск - C++
Добрый день. Помогите найти ошибку в двоичном поиске. Вот код: #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; int...

Двоичный поиск - C++
Помогите пожалуйста с двоичным поиском: нужно найти абитуриента с 287 баллами методом двоичного поиска.. #include &lt;iostream.h&gt; ...

Двоичный поиск - C++
Требуется найти в массиве элементы которые повторяются и элементы которые присутствуют единожды. #include &lt;stdafx.h&gt; #define N 10 ...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru