Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.61/18: Рейтинг темы: голосов - 18, средняя оценка - 4.61
Shab13
1 / 1 / 0
Регистрация: 10.03.2011
Сообщений: 39
1

Двоичный поиск

07.04.2011, 10:17. Просмотров 3341. Ответов 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
Ответы с готовыми решениями:

Двоичный поиск
Формат входных данных В первой строке входных данных содержатся натуральные...

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

Двоичный поиск
Помогите пожалуйста с двоичным поиском: нужно найти абитуриента с 287 баллами...

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

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

22
fasked
Эксперт С++
4982 / 2561 / 241
Регистрация: 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
Эксперт С++
4982 / 2561 / 241
Регистрация: 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
4205 / 1768 / 211
Регистрация: 24.11.2009
Сообщений: 27,565
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Эксперт С++
8102 / 4953 / 1436
Регистрация: 29.11.2010
Сообщений: 13,439
11.04.2011, 10:34 8
до 13/12/2012
1
taras atavin
4205 / 1768 / 211
Регистрация: 24.11.2009
Сообщений: 27,565
11.04.2011, 10:35 9
Кстати, бинарный поиск используется в деревьях, в крайнем случае в корягах, но ни как не в массивах.
0
fasked
Эксперт С++
4982 / 2561 / 241
Регистрация: 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
4205 / 1768 / 211
Регистрация: 24.11.2009
Сообщений: 27,565
12.04.2011, 12:42 12
Цитата Сообщение от fasked Посмотреть сообщение
Если массив отсортирован, то почему нет? Очень
Потому, что в массиве, даже отсортированном, на сколько после сравнения отступить от текущего элмента, чтоб получился бинарынй поиск. Сравнил ты с первым элементом, он оказался меньше, переходишь ко второму и считаешь поиск бинарным? Придётся тебя разочаровать, но это последовательный поиск.
0
fasked
Эксперт С++
4982 / 2561 / 241
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
12.04.2011, 16:04 13
Цитата Сообщение от taras atavin Посмотреть сообщение
Потому, что в массиве, даже отсортированном, на сколько после сравнения отступить от текущего элмента, чтоб получился бинарынй поиск. Сравнил ты с первым элементом, он оказался меньше, переходишь ко второму и считаешь поиск бинарным? Придётся тебя разочаровать, но это последовательный поиск.
Либо мы не понимаем друг друга, либо Вы не понимаете сути бинарного поиска. Если массив отсортирован, то для поиска элемента "отступать" необходимо ровно на половину текущего интервала поиска. В итоге сложность получится в лучшем случае O(logn). В худшем случае O(n). Это касается и двоичных деревьев поиска тоже. Именно двоичных, к которым не применяются алгоритмы балансировки. Видели когда-нибудь такое дерево?
Название: binary_tree.png
Просмотров: 101

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

Если речь идет о касательно конкретно этой задачи, то я и не говорил, что бинарный поиск (или метод деления пополам) здесь должен быть, я говорил, что задание "бредовое". То есть в этой задаче никакого бинарного поиска и не будет - будет просто отсортированный массив. Здесь как такового поиска не будет вообще
0
fasked
Эксперт С++
4982 / 2561 / 241
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
12.04.2011, 16:07 14
Цитата Сообщение от taras atavin Посмотреть сообщение
Сравнил ты с первым элементом, он оказался меньше, переходишь ко второму и считаешь поиск бинарным?
И начинать надо кстати не с первого элемента, а с n/2.
0
fasked
Эксперт С++
4982 / 2561 / 241
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
12.04.2011, 16:20 15
Они похожи, не правда ли?
0
Миниатюры
Двоичный поиск  
fasked
Эксперт С++
4982 / 2561 / 241
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
12.04.2011, 16:31 16
Примерное решение задачи (не проверял):
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
#include <stdio.h>
#include <stdlib.h>
 
#define SIZE 10
 
int comparator(const void *a, const void *b) {
    return -(*(int *)a - *(int *)b);
}
 
int main() {
    int i, bsize = 0;
    int a[SIZE] = { 2, 5, 4, 1, 4, 2, 8, 7, 5, 4 };
    int b[SIZE] = { 0 };
 
    // сортировка
    qsort(a, SIZE, sizeof(int), comparator);
 
    // поиск неповторяющихся элементов
    if (a[0] != a[1])
        b[bsize++] = a[0];
    if (a[SIZE-1] != a[SIZE-2])
        b[bsize++] = a[SIZE-1];
 
    for (i = 1; i < SIZE - 1; ++i) {
        if (a[i-1] != a[i] && a[i] != a[i+1])
            b[bsize++] = a[i];
    }
 
    // вывод 
    for (i = 0; i < SIZE; ++i) 
        printf("%d ", a[i]);
 
    printf("\n");
    for (i = 0; i < bsize; ++i)
        printf("%d ", b[i]);
 
    return 0;
}
1
popov654
32 / 32 / 7
Регистрация: 09.04.2011
Сообщений: 119
13.04.2011, 04:13 17
fasked, а не подскажете для общего развития (мы C/C++ изучали аж в конце 2009-ого, так что уже многое забылось), почему comparator реализован именно так? Через адреса? То есть как я понял передаются указатели на переменные, потом происходит разыменование (что логично), потом зачем-то опять... В общем я слегка запутался О_о
0
fasked
Эксперт С++
4982 / 2561 / 241
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
13.04.2011, 21:22 18
Цитата Сообщение от popov654 Посмотреть сообщение
почему comparator реализован именно так? Через адреса?
Через указатели, потому что, если выполнять сортировку структур, то передавать по значению будет слишком накладно представьте себе структуру размером сто байт или больше, указатель же всегда 4 или 8 байт.
Цитата Сообщение от popov654 Посмотреть сообщение
То есть как я понял передаются указатели на переменные, потом происходит разыменование (что логично), потом зачем-то опять... В общем я слегка запутался
Сначала приведение типа к указателю на int (чтобы можно было сравнить), потом разыменование.
0
popov654
32 / 32 / 7
Регистрация: 09.04.2011
Сообщений: 119
13.04.2011, 21:36 19
Так если у Вас будет передаваться указатель на структуру, Вы приводите его к типу (int*), разыменовываете и делаете вычитание, то что получится в итоге? Вычитать можно вроде бы только целые, но что реально будет вычитаться в случае структуры в качестве аргумента?

Принцип возвращаемого значения вполне понятен (отрицательное, в случае если первый аргумент больше, ноль если равны, иначе положительное), но насчёт вычитания пока не понял...
0
fasked
Эксперт С++
4982 / 2561 / 241
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
13.04.2011, 21:43 20
Цитата Сообщение от popov654 Посмотреть сообщение
Так если у Вас будет передаваться указатель на структуру, Вы приводите его к типу (int*), разыменовываете и делаете вычитание, то что получится в итоге? Вычитать можно вроде бы только целые, но что реально будет вычитаться в случае структуры в качестве аргумента?
Компаратор "подгоняется" под конкретный тип данных и конкретный случай вообще, тот что выше сделан для int и сортировки по убыванию. Если делать компаратор для структур, то и приводить тип, само собой, надо будет к типу этой структуры.
Цитата Сообщение от popov654 Посмотреть сообщение
Принцип возвращаемого значения вполне понятен (отрицательное, в случае если первый аргумент больше, ноль если равны, иначе положительное), но насчёт вычитания пока не понял...
Если принцип возвращаемого значения понятен, то тогда с вычитанием все совсем просто. Есть два числа x и y. Если x < y, то x - y < 0. Если x > y, то x - y > 0, если x == y, то x - y == 0. Унарный минус для всего выражения изменяют ситуацию на прямо противоположную. Если x < y, то -(x - y) > 0. Если x > y, то -(x - y) < 0, если x == y, то -(x - y) == 0. Что и делает компаратор пригодным для сортировки по убыванию, а не по возрастанию. Здесь применяется банальнейшая арифметика. Как я уже говорил компаратор подстраивается под конкретный случай, для целых чисел это (на мой взгляд) одна из наиболее коротких записей. В общем виде тело функции-компаратора выглядело бы так:
C
1
2
3
if (x < y) return -1;
else if (x > y) return 1;
else return 0;
И самое главное как всегда забыл сказать . Не обязательно возвращать -1 или 1, достаточно возвращать значение меньшее нуля или большее нуля. Это все объясняет
0
13.04.2011, 21:43
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.04.2011, 21:43

Двоичный поиск
Добрый день. Помогите найти ошибку в двоичном поиске. Вот код: #include...

Нерекурсивный двоичный поиск
необходимо написать на С++ двоичный поиск в рекурсивном варианте. вот пример...

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


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

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

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