Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.90/21: Рейтинг темы: голосов - 21, средняя оценка - 4.90
ТимурКаримов
0 / 0 / 0
Регистрация: 15.12.2015
Сообщений: 16
1

Бинарный поиск для нахождения количества повторяющихся элементов

18.03.2016, 12:34. Просмотров 4016. Ответов 6
Метки нет (Все метки)

Здравствуйте.
Стоит следующая несложная задача:
Дан массив (отсортированный).
Например
1 1 1 4 5 6 6 6 6 6 6 6
При вводе числа 6 на выходе должны получить
7.
Иными словами, показать количество повторений искомого элемента.
Была идея сделать сперва бинарный поиск элемента с левой стороны, потом с правой, а после отнять координаты и +1, и имеем количество элементов.
Но, алгоритм должен работать O(logn). Если я буду использовать сразу 2 почти аналогичные функций бинарного поиска, сохранится ли эта сложность, или возрастёт?
Если есть какие-то идеи, как сделать быстрее, буду признателен!

Спасибо
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.03.2016, 12:34
Ответы с готовыми решениями:

Бинарный поиск для нахождения нечетных чисел
Подскажите пожалуйста как этот алгоритм линейного поиска обернуть в бинарный поиск for(int i =...

Функция для нахождения количества элементов в бинарном дереве
Помогите написать функцию для нахождения количества элементов в бинарном дереве. реализуйте...

Массив: Написать программу для нахождения количества отрицательных элементов строки матрицы
Здравствуйте. Нужна очень помощь. Задана числовая матрица А. Написать программу для нахождения...

Вставить функцию в код по подсчету времени на нахождения ключа в массиве (бинарный поиск)
помогите вставить функцию в код по подсчету времени на нахождения ключа в массиве(бинарный поиск) ...

Нахождения количества натуральных элементов в масиве
Задача по масивам : Разроботать програму нахождения количества натуральных элементов в масиве...

6
Usaga
Эксперт .NET
6759 / 4714 / 819
Регистрация: 21.01.2016
Сообщений: 18,201
Завершенные тесты: 2
18.03.2016, 13:23 2
Бинарный поиск здесь вполне уместен. Возможно ты что-то другое понимаешь под бинарным поиском?
0
ТимурКаримов
0 / 0 / 0
Регистрация: 15.12.2015
Сообщений: 16
18.03.2016, 13:49  [ТС] 3
Под бинарным поиском я понимаю алгоритм, который найдёт первый левый элемент, который мне нужен.

C++
1
2
3
4
5
6
7
8
9
10
int n = 10;  // длина массива
int key; //искомый элемент 
int left = 0; int x1; //найденный элемент 
int table [n]; 
int right = n - 1; 
while (left <= right){
     if (table[n] == x) x1 = n; 
     if (table[n] > x) right = n - 1; 
     else left = n + 1;  
}
Поменяв местами действия в последних if и else, мы получим элемент первый с правой стороны. Так понимаю, мне нужно написать два этих алгоритма (для левого и для правого). А потом от правого отнять левый и прибавить 1.
И вопрос сразу появляется, не возрастёт ли сложность алгоритма, если я буду использовать сперва одну функцию, а потом вторую, почти такую же.

Спасибо!!
0
Usaga
Эксперт .NET
6759 / 4714 / 819
Регистрация: 21.01.2016
Сообщений: 18,201
Завершенные тесты: 2
18.03.2016, 14:07 4
Цитата Сообщение от ТимурКаримов Посмотреть сообщение
Под бинарным поиском я понимаю алгоритм, который найдёт первый левый элемент, который мне нужен.
И это неправильное понимание. Двоичный поиск - поиск методом деления массива пополам. Посмотри пример на википедии, там лучше изложено, чем я могу сформулировать...

Добавлено через 3 минуты
В данном случае, двоичный поиск найдёт тебе одну из шестёрок (если ты будешь искать шестёрку), а там ты уже должен будешь подсчитать количество шестёрок иным способом - к примеру пройтись по массиву вниз и в верх от найденной позиции...
1
ТимурКаримов
0 / 0 / 0
Регистрация: 15.12.2015
Сообщений: 16
18.03.2016, 17:10  [ТС] 5
Понял. А сам этот проход по массиву, циклом for или while, он ведь повысит сложность алгоритма?
Или всё равно останется O(logn)?

Спасибо за подсказки

Добавлено через 24 минуты
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int binary_right (int [] table, int x, int left, int right, int tmp){
        int s;
        int x1 = -1; 
        while (left <= right){
            s = (left+right)/2; 
            if (table[s] == x) x1 = s; 
            if (table[s] > x) right = s - 1; 
            else left = s + 1; 
        }
        while (table[x1] == x){
            tmp++; 
            x1--; 
        }
        return tmp;
    }
Что-то в этом роде. Сложность O(logn) сохранится?
0
SlavaSSU
219 / 164 / 47
Регистрация: 17.07.2012
Сообщений: 587
18.03.2016, 17:24 6
Лучший ответ Сообщение было отмечено ТимурКаримов как решение

Решение

ТимурКаримов, надо сначала бинпоиском найти первый элемент, строго больше данного и вычесть позицию первого элемента, больше либо равного данному. Т.е. делаешь два бинпоиска. Сложность от этого не изменится. Такие алгоритмы уже есть в стандартной библиотеке и называются upper_bound() и lower_bound() соответственно. А сложность того что ты написал в последнем сообщении - линейная.
1
ТимурКаримов
0 / 0 / 0
Регистрация: 15.12.2015
Сообщений: 16
19.03.2016, 20:20  [ТС] 7
Большое спасибо за ответы!

Сделал всё же немножко по-другому.
Одной функцией сперва ищу элемент с правой стороны, после - с левой.
Отнимаю координаты и прибавляю 1.

Вот мой код:
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int binary_search (int [] table, int key, int left, int right, int side){
        int s = 0; 
        int x1 = -1; 
        while (left <= right){
            s = (left + right)/2; 
            if (table[s] == key) x1 = s; 
            if (side == 0){
                if (table[s] > key) right = s - 1; 
                else left = s + 1; 
            }
            else {
                if (table[s] < key) left = s + 1; 
                else right = s - 1; 
            }
        }
        return x1; 
    }
И в main вызываю
Java
1
2
z1 = binary_search(table, x, 0, n -1, 0);
z = binary_search(table, x, 0, n -1, 1);
Всё работает. Снова не могу понять, O(log(n)) сохраняется, или эти if-ы всё портят? По идее не должны: они ведь прибавляют константу к вычислению сложности?
0
19.03.2016, 20:20
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.03.2016, 20:20

Поиск повторяющихся элементов в массиве
Если повторяющихся элементов 2 (например: 1 2 3 1) - то выдвигает 1 элемент(правильно), если же их...

Поиск повторяющихся (строковых) элементов в массиве
Друзья помогите пожалуйста встала такая задача. Есть 3 файла со строчками нужно найти и вывести...

Поиск повторяющихся элементов динамического массива
Задача: задается целочисленная матрица &quot;А&quot; из M строк и N столбцов. Сформировать вектор &quot;В&quot; из М...


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

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

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