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

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

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

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

07.04.2011, 10:17. Просмотров 3207. Ответов 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
Эксперт С++
4948 / 2528 / 180
Регистрация: 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 / 2
Регистрация: 09.04.2011
Сообщений: 119
13.04.2011, 04:13 #17
fasked, а не подскажете для общего развития (мы C/C++ изучали аж в конце 2009-ого, так что уже многое забылось), почему comparator реализован именно так? Через адреса? То есть как я понял передаются указатели на переменные, потом происходит разыменование (что логично), потом зачем-то опять... В общем я слегка запутался О_о
0
fasked
Эксперт С++
4948 / 2528 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
13.04.2011, 21:22 #18
Цитата Сообщение от popov654 Посмотреть сообщение
почему comparator реализован именно так? Через адреса?
Через указатели, потому что, если выполнять сортировку структур, то передавать по значению будет слишком накладно представьте себе структуру размером сто байт или больше, указатель же всегда 4 или 8 байт.
Цитата Сообщение от popov654 Посмотреть сообщение
То есть как я понял передаются указатели на переменные, потом происходит разыменование (что логично), потом зачем-то опять... В общем я слегка запутался
Сначала приведение типа к указателю на int (чтобы можно было сравнить), потом разыменование.
0
popov654
32 / 32 / 2
Регистрация: 09.04.2011
Сообщений: 119
13.04.2011, 21:36 #19
Так если у Вас будет передаваться указатель на структуру, Вы приводите его к типу (int*), разыменовываете и делаете вычитание, то что получится в итоге? Вычитать можно вроде бы только целые, но что реально будет вычитаться в случае структуры в качестве аргумента?

Принцип возвращаемого значения вполне понятен (отрицательное, в случае если первый аргумент больше, ноль если равны, иначе положительное), но насчёт вычитания пока не понял...
0
fasked
Эксперт С++
4948 / 2528 / 180
Регистрация: 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
popov654
32 / 32 / 2
Регистрация: 09.04.2011
Сообщений: 119
13.04.2011, 22:58 #21
Да это как раз я и так понял, вопрос не в этом был)

Вот видите, Вы сами согласились, что такой компаратор пригоден только для целых. Но тогда зачем заморачиваться с приведением типа? Писали бы в сигнатуре (const int *a, const int *b)...
Не говоря уже о том, что в случае целых можно вообще без указателей, они больше 8 байт не занимают
0
fasked
Эксперт С++
4948 / 2528 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
13.04.2011, 23:12 #22
Цитата Сообщение от popov654 Посмотреть сообщение
Вот видите, Вы сами согласились, что такой компаратор пригоден только для целых. Но тогда зачем заморачиваться с приведением типа? Писали бы в сигнатуре (const int *a, const int *b)...
Не говоря уже о том, что в случае целых можно вообще без указателей, они больше 8 байт не занимают
Компаратор с другим прототипом не подойдет для функции qsort
0
popov654
32 / 32 / 2
Регистрация: 09.04.2011
Сообщений: 119
14.04.2011, 00:51 #23
А-а-а...
Так она системная...
Сорри. Тогда ОК) Мы просто все эти сортировки руками писали, я даже не очень был в курсе, что она реализована там
0
14.04.2011, 00:51
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.04.2011, 00:51
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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