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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.76
Shab13
1 / 1 / 0
Регистрация: 10.03.2011
Сообщений: 39
07.04.2011, 10:17     Двоичный поиск #1
Требуется найти в массиве элементы которые повторяются и элементы которые присутствуют единожды.

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;
}
Можно ли как-то дописать в этот код?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.04.2011, 10:17     Двоичный поиск
Посмотрите здесь:

C++ Нерекурсивный двоичный поиск
Двоичный поиск C++
Двоичный поиск C++
C++ Двоичный поиск в map
двоичный поиск C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
07.04.2011, 10:27     Двоичный поиск #2
Цитата Сообщение от Shab13 Посмотреть сообщение
Требуется найти в массиве элементы которые повторяются и элементы которые присутствуют единожды
Так, а при чем здесь бинарный поиск, или это с его помощью найти надо?
Shab13
1 / 1 / 0
Регистрация: 10.03.2011
Сообщений: 39
07.04.2011, 10:28  [ТС]     Двоичный поиск #3
Цитата Сообщение от fasked Посмотреть сообщение
Так, а при чем здесь бинарный поиск, или это с его помощью найти надо?
Да, надо найти с помощью бинарного поиска.
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
07.04.2011, 10:32     Двоичный поиск #4
Цитата Сообщение от Shab13 Посмотреть сообщение
Да, надо найти с помощью бинарного поиска.
Это же бред, бинарный поиск используется для поиска конкретного элемента, с целью сократить время поиска, чтобы оно было меньше линейного. А в этой задаче все равно придется просматривать весь массив и бинарный поиск здесь ни к чему. Вот только если конечно, я как-то неправильно понял задание и надо узнать, повторяется ли то число, которое ищется, а не вообще все числа.
Shab13
1 / 1 / 0
Регистрация: 10.03.2011
Сообщений: 39
07.04.2011, 10:42  [ТС]     Двоичный поиск #5
Да сам толком не понял Наверное надо создать ещё один массив, в котором будут елементы, что используются только один раз.
Shab13
1 / 1 / 0
Регистрация: 10.03.2011
Сообщений: 39
11.04.2011, 10:23  [ТС]     Двоичный поиск #6
Помогите плз сделать до четверга.
taras atavin
Ушёл с форума.
 Аватар для 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? Или ещё до какого нибудь?
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4925 / 2668 / 243
Регистрация: 29.11.2010
Сообщений: 7,421
11.04.2011, 10:34     Двоичный поиск #8
до 13/12/2012
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
11.04.2011, 10:35     Двоичный поиск #9
Кстати, бинарный поиск используется в деревьях, в крайнем случае в корягах, но ни как не в массивах.
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
11.04.2011, 14:25     Двоичный поиск #10
Цитата Сообщение от taras atavin Посмотреть сообщение
Кстати, бинарный поиск используется в деревьях, в крайнем случае в корягах, но ни как не в массивах.
Если массив отсортирован, то почему нет? Очень даже используется. Можно взглянуть хотя бы на это - /binary_search/.
Цитата Сообщение от Shab13 Посмотреть сообщение
Помогите плз сделать до четверга.
Мы не можем тебе помочь. Почему? Я это описывал уже выше - задание бредовое. А за прошедшее время ты мог бы его уточнить кстати.
Shab13
1 / 1 / 0
Регистрация: 10.03.2011
Сообщений: 39
12.04.2011, 12:09  [ТС]     Двоичный поиск #11
Цитата Сообщение от fasked Посмотреть сообщение
Если массив отсортирован, то почему нет? Очень даже используется. Можно взглянуть хотя бы на это - /binary_search/.

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

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

Если речь идет о касательно конкретно этой задачи, то я и не говорил, что бинарный поиск (или метод деления пополам) здесь должен быть, я говорил, что задание "бредовое". То есть в этой задаче никакого бинарного поиска и не будет - будет просто отсортированный массив. Здесь как такового поиска не будет вообще
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
12.04.2011, 16:07     Двоичный поиск #14
Цитата Сообщение от taras atavin Посмотреть сообщение
Сравнил ты с первым элементом, он оказался меньше, переходишь ко второму и считаешь поиск бинарным?
И начинать надо кстати не с первого элемента, а с n/2.
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
12.04.2011, 16:20     Двоичный поиск #15
Они похожи, не правда ли?
Миниатюры
Двоичный поиск  
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 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;
}
popov654
 Аватар для popov654
31 / 31 / 2
Регистрация: 09.04.2011
Сообщений: 114
13.04.2011, 04:13     Двоичный поиск #17
fasked, а не подскажете для общего развития (мы C/C++ изучали аж в конце 2009-ого, так что уже многое забылось), почему comparator реализован именно так? Через адреса? То есть как я понял передаются указатели на переменные, потом происходит разыменование (что логично), потом зачем-то опять... В общем я слегка запутался О_о
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
13.04.2011, 21:22     Двоичный поиск #18
Цитата Сообщение от popov654 Посмотреть сообщение
почему comparator реализован именно так? Через адреса?
Через указатели, потому что, если выполнять сортировку структур, то передавать по значению будет слишком накладно представьте себе структуру размером сто байт или больше, указатель же всегда 4 или 8 байт.
Цитата Сообщение от popov654 Посмотреть сообщение
То есть как я понял передаются указатели на переменные, потом происходит разыменование (что логично), потом зачем-то опять... В общем я слегка запутался
Сначала приведение типа к указателю на int (чтобы можно было сравнить), потом разыменование.
popov654
 Аватар для popov654
31 / 31 / 2
Регистрация: 09.04.2011
Сообщений: 114
13.04.2011, 21:36     Двоичный поиск #19
Так если у Вас будет передаваться указатель на структуру, Вы приводите его к типу (int*), разыменовываете и делаете вычитание, то что получится в итоге? Вычитать можно вроде бы только целые, но что реально будет вычитаться в случае структуры в качестве аргумента?

Принцип возвращаемого значения вполне понятен (отрицательное, в случае если первый аргумент больше, ноль если равны, иначе положительное), но насчёт вычитания пока не понял...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.04.2011, 21:43     Двоичный поиск
Еще ссылки по теме:

Приближенный двоичный поиск C++
двоичный поиск C++
Двоичный поиск C++

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

Или воспользуйтесь поиском по форуму:
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 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, достаточно возвращать значение меньшее нуля или большее нуля. Это все объясняет
Yandex
Объявления
13.04.2011, 21:43     Двоичный поиск
Ответ Создать тему
Опции темы

Текущее время: 03:10. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru