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

@Shab13 · Регистрация: 10.03.2011

Author24 — интернет-сервис помощи студентам

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

C++

#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;
}

Можно ли как-то дописать в этот код?

@fasked · 07.04.2011, 10:27

Сообщение от Shab13

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

Так, а при чем здесь бинарный поиск, или это с его помощью найти надо?

@Shab13 · 07.04.2011, 10:28 **[ТС]**

Сообщение от fasked

Так, а при чем здесь бинарный поиск, или это с его помощью найти надо?

Да, надо найти с помощью бинарного поиска.

@fasked · 07.04.2011, 10:32

Сообщение от Shab13

Да, надо найти с помощью бинарного поиска.

Это же бред, бинарный поиск используется для поиска конкретного элемента, с целью сократить время поиска, чтобы оно было меньше линейного. А в этой задаче все равно придется просматривать весь массив и бинарный поиск здесь ни к чему. Вот только если конечно, я как-то неправильно понял задание и надо узнать, повторяется ли то число, которое ищется, а не вообще все числа.

@Shab13 · 07.04.2011, 10:42 **[ТС]**

Да сам толком не понял

Наверное надо создать ещё один массив, в котором будут елементы, что используются только один раз.

@Shab13 · 11.04.2011, 10:23 **[ТС]**

Помогите плз сделать до четверга.

@taras atavin · 11.04.2011, 10:31

До какого именно? До 14/04/2011, 21/04/2011, 28/04/2011, 4/05/2011, 11/05/2011, 18/05/2011, или 25/05/2011? Или ещё до какого нибудь?

MrGluck · 11.04.2011, 10:34

до 13/12/2012

@taras atavin · 11.04.2011, 10:35

Кстати, бинарный поиск используется в деревьях, в крайнем случае в корягах, но ни как не в массивах.

@fasked · 11.04.2011, 14:25

Сообщение от taras atavin

Кстати, бинарный поиск используется в деревьях, в крайнем случае в корягах, но ни как не в массивах.

Если массив отсортирован, то почему нет? Очень даже используется. Можно взглянуть хотя бы на это - /binary_search/.

Сообщение от Shab13

Помогите плз сделать до четверга.

Мы не можем тебе помочь. Почему? Я это описывал уже выше - задание бредовое. А за прошедшее время ты мог бы его уточнить кстати.

@Shab13 · 12.04.2011, 12:09 **[ТС]**

Сообщение от fasked

Если массив отсортирован, то почему нет? Очень даже используется. Можно взглянуть хотя бы на это - /binary_search/.

Мы не можем тебе помочь. Почему? Я это описывал уже выше - задание бредовое. А за прошедшее время ты мог бы его уточнить кстати.

Да этих преподов фиг поймеш, переспросил, условие такое: Дан массив А, отсортировать его по убыванию, найти элементы которые встречаются единожды и перенести их в массив В.
Извиняюсь за неудобства)
П.С. До четверга 14.04.2011

@taras atavin · 12.04.2011, 12:42

Сообщение от fasked

Если массив отсортирован, то почему нет? Очень

Потому, что в массиве, даже отсортированном, на сколько после сравнения отступить от текущего элмента, чтоб получился бинарынй поиск. Сравнил ты с первым элементом, он оказался меньше, переходишь ко второму и считаешь поиск бинарным? Придётся тебя разочаровать, но это последовательный поиск.

@fasked · 12.04.2011, 16:04

Сообщение от taras atavin

Потому, что в массиве, даже отсортированном, на сколько после сравнения отступить от текущего элмента, чтоб получился бинарынй поиск. Сравнил ты с первым элементом, он оказался меньше, переходишь ко второму и считаешь поиск бинарным? Придётся тебя разочаровать, но это последовательный поиск.

Либо мы не понимаем друг друга, либо Вы не понимаете сути бинарного поиска. Если массив отсортирован, то для поиска элемента "отступать" необходимо ровно на половину текущего интервала поиска. В итоге сложность получится в лучшем случае O(logn). В худшем случае O(n). Это касается и двоичных деревьев поиска тоже. Именно двоичных, к которым не применяются алгоритмы балансировки. Видели когда-нибудь такое дерево?
Название: binary_tree.png
Просмотров: 111

Размер: 7.3 Кб

Название: binary_tree.png
Просмотров: 111

Размер: 7.3 Кб

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

Если речь идет о касательно конкретно этой задачи, то я и не говорил, что бинарный поиск (или метод деления пополам) здесь должен быть, я говорил, что задание "бредовое". То есть в этой задаче никакого бинарного поиска и не будет - будет просто отсортированный массив. Здесь как такового поиска не будет вообще

@fasked · 12.04.2011, 16:07

Сообщение от taras atavin

Сравнил ты с первым элементом, он оказался меньше, переходишь ко второму и считаешь поиск бинарным?

И начинать надо кстати не с первого элемента, а с n/2.

@fasked · 12.04.2011, 16:20

Они похожи, не правда ли?

@fasked · 12.04.2011, 16:31

Примерное решение задачи (не проверял):

C

#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 · 13.04.2011, 04:13

fasked, а не подскажете для общего развития (мы C/C++ изучали аж в конце 2009-ого, так что уже многое забылось), почему comparator реализован именно так? Через адреса? То есть как я понял передаются указатели на переменные, потом происходит разыменование (что логично), потом зачем-то опять... В общем я слегка запутался О_о

@fasked · 13.04.2011, 21:22

Сообщение от popov654

почему comparator реализован именно так? Через адреса?

Через указатели, потому что, если выполнять сортировку структур, то передавать по значению будет слишком накладно представьте себе структуру размером сто байт или больше, указатель же всегда 4 или 8 байт.

Сообщение от popov654

То есть как я понял передаются указатели на переменные, потом происходит разыменование (что логично), потом зачем-то опять... В общем я слегка запутался

Сначала приведение типа к указателю на int (чтобы можно было сравнить), потом разыменование.

@popov654 · 13.04.2011, 21:36

Так если у Вас будет передаваться указатель на структуру, Вы приводите его к типу (int*), разыменовываете и делаете вычитание, то что получится в итоге? Вычитать можно вроде бы только целые, но что реально будет вычитаться в случае структуры в качестве аргумента?

Принцип возвращаемого значения вполне понятен (отрицательное, в случае если первый аргумент больше, ноль если равны, иначе положительное), но насчёт вычитания пока не понял...

@fasked · 13.04.2011, 21:43

Сообщение от 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, достаточно возвращать значение меньшее нуля или большее нуля. Это все объясняет

@fasked 5043 / 2622 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 1
	12.04.2011, 16:20	15
	Они похожи, не правда ли? Миниатюры 0

@popov654 33 / 33 / 7 Регистрация: 09.04.2011 Сообщений: 119
	13.04.2011, 04:13	17
	fasked, а не подскажете для общего развития (мы C/C++ изучали аж в конце 2009-ого, так что уже многое забылось), почему comparator реализован именно так? Через адреса? То есть как я понял передаются указатели на переменные, потом происходит разыменование (что логично), потом зачем-то опять... В общем я слегка запутался О_о 0

@popov654 33 / 33 / 7 Регистрация: 09.04.2011 Сообщений: 119
	13.04.2011, 21:36	19
	Так если у Вас будет передаваться указатель на структуру, Вы приводите его к типу (int*), разыменовываете и делаете вычитание, то что получится в итоге? Вычитать можно вроде бы только целые, но что реально будет вычитаться в случае структуры в качестве аргумента? Принцип возвращаемого значения вполне понятен (отрицательное, в случае если первый аргумент больше, ноль если равны, иначе положительное), но насчёт вычитания пока не понял... 0

@fasked 5043 / 2622 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 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 5043 / 2622 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 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 4226 / 1795 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	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 Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	11.04.2011, 10:34	8
	до 13/12/2012 1

@taras atavin 4226 / 1795 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	11.04.2011, 10:35	9
	Кстати, бинарный поиск используется в деревьях, в крайнем случае в корягах, но ни как не в массивах. 0

@fasked 5043 / 2622 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 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 4226 / 1795 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	12.04.2011, 12:42	12
	Сообщение от fasked Если массив отсортирован, то почему нет? Очень Потому, что в массиве, даже отсортированном, на сколько после сравнения отступить от текущего элмента, чтоб получился бинарынй поиск. Сравнил ты с первым элементом, он оказался меньше, переходишь ко второму и считаешь поиск бинарным? Придётся тебя разочаровать, но это последовательный поиск. 0

@fasked 5043 / 2622 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 1
	12.04.2011, 16:04	13
	Сообщение от taras atavin Потому, что в массиве, даже отсортированном, на сколько после сравнения отступить от текущего элмента, чтоб получился бинарынй поиск. Сравнил ты с первым элементом, он оказался меньше, переходишь ко второму и считаешь поиск бинарным? Придётся тебя разочаровать, но это последовательный поиск. Либо мы не понимаем друг друга, либо Вы не понимаете сути бинарного поиска. Если массив отсортирован, то для поиска элемента "отступать" необходимо ровно на половину текущего интервала поиска. В итоге сложность получится в лучшем случае O(logn). В худшем случае O(n). Это касается и двоичных деревьев поиска тоже. Именно двоичных, к которым не применяются алгоритмы балансировки. Видели когда-нибудь такое дерево? Сколько потребуется итераций, чтобы найти лист дерева? Правильно - O(n). Судя по Вашей логике, здесь тоже будет последовательный поиск. В бинарных деревьях поиска сложность абсолютно такая же: O(logn) - в лучшем случае и O(n) - в худшем. Если речь идет о касательно конкретно этой задачи, то я и не говорил, что бинарный поиск (или метод деления пополам) здесь должен быть, я говорил, что задание "бредовое". То есть в этой задаче никакого бинарного поиска и не будет - будет просто отсортированный массив. Здесь как такового поиска не будет вообще 0

@fasked 5043 / 2622 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 1
	12.04.2011, 16:07	14
	Сообщение от taras atavin Сравнил ты с первым элементом, он оказался меньше, переходишь ко второму и считаешь поиск бинарным? И начинать надо кстати не с первого элемента, а с n/2. 0

@fasked 5043 / 2622 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 1
	13.04.2011, 21:22	18
	Сообщение от popov654 почему comparator реализован именно так? Через адреса? Через указатели, потому что, если выполнять сортировку структур, то передавать по значению будет слишком накладно представьте себе структуру размером сто байт или больше, указатель же всегда 4 или 8 байт. Сообщение от popov654 То есть как я понял передаются указатели на переменные, потом происходит разыменование (что логично), потом зачем-то опять... В общем я слегка запутался Сначала приведение типа к указателю на int (чтобы можно было сравнить), потом разыменование. 0