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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.76
Shab13
1 / 1 / 0
Регистрация: 10.03.2011
Сообщений: 39
#1

Двоичный поиск - C++

07.04.2011, 10:17. Просмотров 3195. Ответов 22
Метки нет (Все метки)

Требуется найти в массиве элементы которые повторяются и элементы которые присутствуют единожды.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdafx.h>
#define N 10
 
int main(void)
{
    int a[N],v,low,high,i,k;;
    for(i=0;i<N;i++)
    {
        scanf("%d", &a[i]);
    }
    printf("Input value to search -> ");
    scanf("%d",&v);
    low=0; high=N-1;
    for(i=N/2; a[i]!=v; i=(low+high)/2)
        if(a[i]<v) low=i+low;
        else high=i-low;
    printf("Value %d on %d place\n", v, i+1);
    return 0;
}
Можно ли как-то дописать в этот код?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.04.2011, 10:17
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Двоичный поиск (C++):

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

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

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

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

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

Приближенный двоичный поиск - C++
Доброго времени суток, форумчане. Задача такая: В первой строке входных данных содержатся числа N и K (0 &gt; N,K &gt;100001 ). Во второй...

22
fasked
Эксперт С++
4945 / 2525 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
07.04.2011, 10:27 #2
Цитата Сообщение от Shab13 Посмотреть сообщение
Требуется найти в массиве элементы которые повторяются и элементы которые присутствуют единожды
Так, а при чем здесь бинарный поиск, или это с его помощью найти надо?
0
Shab13
1 / 1 / 0
Регистрация: 10.03.2011
Сообщений: 39
07.04.2011, 10:28  [ТС] #3
Цитата Сообщение от fasked Посмотреть сообщение
Так, а при чем здесь бинарный поиск, или это с его помощью найти надо?
Да, надо найти с помощью бинарного поиска.
0
fasked
Эксперт С++
4945 / 2525 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
07.04.2011, 10:32 #4
Цитата Сообщение от Shab13 Посмотреть сообщение
Да, надо найти с помощью бинарного поиска.
Это же бред, бинарный поиск используется для поиска конкретного элемента, с целью сократить время поиска, чтобы оно было меньше линейного. А в этой задаче все равно придется просматривать весь массив и бинарный поиск здесь ни к чему. Вот только если конечно, я как-то неправильно понял задание и надо узнать, повторяется ли то число, которое ищется, а не вообще все числа.
0
Shab13
1 / 1 / 0
Регистрация: 10.03.2011
Сообщений: 39
07.04.2011, 10:42  [ТС] #5
Да сам толком не понял Наверное надо создать ещё один массив, в котором будут елементы, что используются только один раз.
0
Shab13
1 / 1 / 0
Регистрация: 10.03.2011
Сообщений: 39
11.04.2011, 10:23  [ТС] #6
Помогите плз сделать до четверга.
0
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
11.04.2011, 10:31 #7
До какого именно? До 14/04/2011, 21/04/2011, 28/04/2011, 4/05/2011, 11/05/2011, 18/05/2011, или 25/05/2011? Или ещё до какого нибудь?
0
MrGluck
Модератор
Эксперт CЭксперт С++
7423 / 4538 / 673
Регистрация: 29.11.2010
Сообщений: 12,319
11.04.2011, 10:34 #8
до 13/12/2012
1
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
11.04.2011, 10:35 #9
Кстати, бинарный поиск используется в деревьях, в крайнем случае в корягах, но ни как не в массивах.
0
fasked
Эксперт С++
4945 / 2525 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
11.04.2011, 14:25 #10
Цитата Сообщение от taras atavin Посмотреть сообщение
Кстати, бинарный поиск используется в деревьях, в крайнем случае в корягах, но ни как не в массивах.
Если массив отсортирован, то почему нет? Очень даже используется. Можно взглянуть хотя бы на это - /binary_search/.
Цитата Сообщение от Shab13 Посмотреть сообщение
Помогите плз сделать до четверга.
Мы не можем тебе помочь. Почему? Я это описывал уже выше - задание бредовое. А за прошедшее время ты мог бы его уточнить кстати.
0
Shab13
1 / 1 / 0
Регистрация: 10.03.2011
Сообщений: 39
12.04.2011, 12:09  [ТС] #11
Цитата Сообщение от fasked Посмотреть сообщение
Если массив отсортирован, то почему нет? Очень даже используется. Можно взглянуть хотя бы на это - /binary_search/.

Мы не можем тебе помочь. Почему? Я это описывал уже выше - задание бредовое. А за прошедшее время ты мог бы его уточнить кстати.
Да этих преподов фиг поймеш, переспросил, условие такое: Дан массив А, отсортировать его по убыванию, найти элементы которые встречаются единожды и перенести их в массив В.
Извиняюсь за неудобства)
П.С. До четверга 14.04.2011
0
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
12.04.2011, 12:42 #12
Цитата Сообщение от fasked Посмотреть сообщение
Если массив отсортирован, то почему нет? Очень
Потому, что в массиве, даже отсортированном, на сколько после сравнения отступить от текущего элмента, чтоб получился бинарынй поиск. Сравнил ты с первым элементом, он оказался меньше, переходишь ко второму и считаешь поиск бинарным? Придётся тебя разочаровать, но это последовательный поиск.
0
fasked
Эксперт С++
4945 / 2525 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
12.04.2011, 16:04 #13
Цитата Сообщение от taras atavin Посмотреть сообщение
Потому, что в массиве, даже отсортированном, на сколько после сравнения отступить от текущего элмента, чтоб получился бинарынй поиск. Сравнил ты с первым элементом, он оказался меньше, переходишь ко второму и считаешь поиск бинарным? Придётся тебя разочаровать, но это последовательный поиск.
Либо мы не понимаем друг друга, либо Вы не понимаете сути бинарного поиска. Если массив отсортирован, то для поиска элемента "отступать" необходимо ровно на половину текущего интервала поиска. В итоге сложность получится в лучшем случае O(logn). В худшем случае O(n). Это касается и двоичных деревьев поиска тоже. Именно двоичных, к которым не применяются алгоритмы балансировки. Видели когда-нибудь такое дерево?
Название: binary_tree.png
Просмотров: 98

Размер: 7.3 Кб
Сколько потребуется итераций, чтобы найти лист дерева? Правильно - O(n). Судя по Вашей логике, здесь тоже будет последовательный поиск. В бинарных деревьях поиска сложность абсолютно такая же: O(logn) - в лучшем случае и O(n) - в худшем.

Если речь идет о касательно конкретно этой задачи, то я и не говорил, что бинарный поиск (или метод деления пополам) здесь должен быть, я говорил, что задание "бредовое". То есть в этой задаче никакого бинарного поиска и не будет - будет просто отсортированный массив. Здесь как такового поиска не будет вообще
0
fasked
Эксперт С++
4945 / 2525 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
12.04.2011, 16:07 #14
Цитата Сообщение от taras atavin Посмотреть сообщение
Сравнил ты с первым элементом, он оказался меньше, переходишь ко второму и считаешь поиск бинарным?
И начинать надо кстати не с первого элемента, а с n/2.
0
fasked
Эксперт С++
4945 / 2525 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
12.04.2011, 16:20 #15
Они похожи, не правда ли?
0
Миниатюры
Двоичный поиск  
12.04.2011, 16:20
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.04.2011, 16:20
Привет! Вот еще темы с ответами:

Двоичный поиск в map - C++
Здравствуйте. Помогите разобраться в следующей проблеме. В общем, мне нужно реализовать двоичный поиск в map по ключам. Понятное дело,...

Двоичный(бинарный) поиск - C++
Столкнулся с такой проблемой. использую бинарный поиск в упорядоченном массиве чисел для поиска количества повторений нужного мне числа К...

Нерекурсивный двоичный поиск - C++
необходимо написать на С++ двоичный поиск в рекурсивном варианте. вот пример рекурсивной ф-ции двоичного поиска: int BinSerch(int...

Двоичный (бинарный) поиск - C++
Вот такой вот вопрос: Есть например такой линейный массив 1 1 1 1 2 3 4 5 6 Вводят какое-то число и нужно проверить сколько...


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

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

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