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

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

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

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

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

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

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

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@Shab13 1 / 1 / 0 Регистрация: 10.03.2011 Сообщений: 39
	07.04.2011, 10:42 [ТС]
	Да сам толком не понял Наверное надо создать ещё один массив, в котором будут елементы, что используются только один раз. 0

@Shab13 1 / 1 / 0 Регистрация: 10.03.2011 Сообщений: 39
	11.04.2011, 10:23 [ТС]
	Помогите плз сделать до четверга. 0

@taras atavin 4226 / 1796 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	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? Или ещё до какого нибудь? 0

MrGluck Форумчанин 8216 / 5047 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	11.04.2011, 10:34
	до 13/12/2012 1

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

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

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

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