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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 51, средняя оценка - 4.84
DrSMERTb
60 / 36 / 4
Регистрация: 12.11.2010
Сообщений: 816
#1

Нужен простой пример бинарного поиска - C++

28.12.2011, 14:02. Просмотров 6735. Ответов 9
Метки нет (Все метки)

Всем доброго времени суток. Кто может привести какой нибудь простенький пример бинарного поиска (будем считать что отсортированный массив уже есть)?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.12.2011, 14:02
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Нужен простой пример бинарного поиска (C++):

Нужен совет по алгоритму приближенного бинарного поиска - C++
Задача такова: Реализуйте алгоритм приближенного бинарного поиска. Входные данные В первой строке входных данных содержатся числа...

Нужен простой пример передачи одной функции или метода в другую функцию или метод - C++
Собственно сабж. Не знаю, как сделать. Как это выглядит синтаксически? Пробовал по разному но не получается Пробовал так. Покажите...

Дерево бинарного поиска - C++
Никак не могу понять как изменить бинарный поиск. Код выводит значения элементов для которых высота левого поддерева больше высоты правого,...

Дерево бинарного поиска - C++
Всем привет! Есть рабочий код бинарного поиска template <class Item, class Key> class ST { private: struct node { Item item;...

Сложность бинарного поиска - C++
Добрый вечер, решал данную задачу: Девочка загадала число от 1 до N. За какое наименьшее количество вопросов вида «Загаданное тобой...

Реализация бинарного поиска - C++
Здравствуйте. Решил реализовать на С++ бинарный поиск. Вместо массива я взял vector (думаю особой роли это не играет), все бы хорошо, НО....

9
ValeryLaptev
Эксперт С++
1042 / 821 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
28.12.2011, 14:09 #2
Цитата Сообщение от DrSMERTb Посмотреть сообщение
Всем доброго времени суток. Кто может привести какой нибудь простенький пример бинарного поиска (будем считать что отсортированный массив уже есть)?
А просто погуглить - никак? Дофига в сети примеров.
0
DrSMERTb
60 / 36 / 4
Регистрация: 12.11.2010
Сообщений: 816
28.12.2011, 14:10  [ТС] #3
Не писал бы сюда если б не искал до этого. Посмотрел примеры понять не понял, так поэтому сюда и отписал.
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,289
Записей в блоге: 2
Завершенные тесты: 1
28.12.2011, 14:13 #4
В STL есть binary_search. Подробнее тут.
Пример:
есть массив
C++
1
1 2 3 4 5
Нам надо узнать, есть ли в нем число 4.
Делим пополам. 5/2=2. Смотрим 2 число. Это 2, 2<4, значит надо искать от 2 элемента до последнего.
Теперь урезанный массив:
C++
1
3 4 5
.
Делим его пополам, 3/2=1. Смотрим 1 число - 3. 3<4, значит урезаем.

Массив:
C++
1
4 5
Делим пополам, 2/1=1. Смотрим 1 число - 4, 4=4, значит выходим из поиска, и возвращаем позицию.
1
DrSMERTb
60 / 36 / 4
Регистрация: 12.11.2010
Сообщений: 816
28.12.2011, 14:15  [ТС] #5
Ну это я понимаю, а как это будет в программе выглядеть?
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,289
Записей в блоге: 2
Завершенные тесты: 1
28.12.2011, 14:16 #6
Wikipedia
0
DrSMERTb
60 / 36 / 4
Регистрация: 12.11.2010
Сообщений: 816
28.12.2011, 15:20  [ТС] #7
Тот пример на который вы дали ссылку реализует поиск элемента, загнав его при этом в оперативку и там с ним и работает. А можно ли как нибудь реализовать поиск без этого?

Добавлено через 5 минут
Вот примерно как здесь,
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream.h>
int BinarySearch(int [], int, int, int);
void PrintRow(int [], int, int);
const int arraySize = 15;
void main( void )
{
 int a[arraySize], key, result;
 // инициализация элементов массива
 for ( int i = 0; i < arraySize; i++) 
 a[i] = 2*i; 
 cout << "Input key, a number in [0,28]: ";
 cin >> key;
 // вызов функции BinarySearch и присвоение
 // возвращаемого ею значения переменной result
 result = BinarySearch(a, key, 0, arraySize - 1);
 if(result != -1)
 cout << '\n' << key << " found in " << result 
 << " element of array\n";
 else
 cout << '\n' << key << " not found \n";
}
// Двоичный поиск
int BinarySearch(int b[], int searchKey, int low, int high)
{
 int middle;
 while (low <= high)
 {
 middle = (low + high) / 2;
 PrintRow(b, low, middle, high);
 if (searchKey == b[middle])
 return middle;
 else if (searchKey < b[middle])
 high = middle - 1;
 else
 low = middle + 1;
 }
 return -1;
}
// печать одной строки, показывающей текущую 
// обрабатываемую часть массива
void PrintRow(int b[], int low, int mid, int high)
{
 for(int i = 0; i < arraySize; i++)
 if (i < low || i > high) 
 cout << " "; 
 else 
 {
 if (i * 2 < 10) 
 cout << " ";
 else 
 cout << " "; 
 
 if(i == mid)
 cout << b[i] << '*'; /* отметить среднее значение */
 else 
 cout << b[i] << ' ';
 }
 cout << '\n';
}
Только посмотрите пожалуйста на что он ругается.
0
Ватадот
3 / 3 / 0
Регистрация: 11.01.2011
Сообщений: 155
28.12.2011, 15:23 #8
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
39
40
41
42
43
44
45
46
47
48
int search_binary( int x )
{
    size_t first = 0; /* Pervyj jelement v massive */
    size_t last = N;  /* Jelement v massive, sled. za poslednim */
                      /* Esli prosmatrivaemyj uchastok nepustoj, first<last */
    size_t mid; 
 
    if (N == 0)
    {
         /* massiv pust */
        return ( -1 );
    } 
    else if (m[0] > x)
    {
         /* ne najdeno;  */
        return ( -1 );
    } 
    else if (m[N - 1] < x)
    {
         /* ne najdeno; */
        return ( -1 );
    }
 
    while (first < last)
    {
        mid = first + (last - first) / 2;
 
        if (x <= m[mid])
        {
            last = mid;
        }
        else
        {
            first = mid + 1;
        }
    }
 
    if (m[last] == x)
    {
        /* Iskomyj jelement najden. last - iskomyj indeks */
        return ( last );
 
    } else
    {
        /* Iskomyj jelement ne najden.  */
        return ( -1 );
    }
}
0
DrSMERTb
60 / 36 / 4
Регистрация: 12.11.2010
Сообщений: 816
28.12.2011, 15:46  [ТС] #9
А можете исходник целиком выложить?
0
Oleg
0 / 0 / 0
Регистрация: 09.03.2012
Сообщений: 7
07.07.2014, 23:26 #10
Вот пиши эту функцию (это для С++), где arr - указазтель на массив, size - размер-1, value - то, что ищем. Если элемента нет, то возвращаем -1.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class T>
int bsearch(T *arr, int size, T value)
{
    int l = 0;
    int r = size;
 
    while (l <= r)
    {
        int mid = l + (r - l) / 2;
                if (arr[mid] == value) return mid;
        if (arr[mid] < value) l = ++mid;
        if (arr[mid] > value) r = --mid;
    }
    return -1;
}
Примерение:

C++
1
2
3
4
5
int arr[] = {1,2,4,5,6,7,8,9};
int main()
{
    bsearch(arr, sizeof(arr)/sizeof(int) - 1, 4);
}
0
07.07.2014, 23:26
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.07.2014, 23:26
Привет! Вот еще темы с ответами:

Простой пример на С++ - C++
a - типа int задаем

Итератор дерева бинарного поиска - C++
Если у нас в качестве коллекции выступают вектора, очереди, стеки и т.п. то там вроде бы всё понятно инкремент, декремент итератора...

Реализация бинарного дерева поиска - C++
Задача: Реализация бинарного дерева поиска Компилируется нормально, а при запуске выбивает ошибку : &quot;Необработанное исключение по адресу...

Объясните принцип бинарного поиска - C++
Можно, пожалуйста, пример или принцип бинарного поиска. С++ для очень сильно начинающих.


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

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

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