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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 51, средняя оценка - 4.84
DrSMERTb
 Аватар для DrSMERTb
59 / 35 / 4
Регистрация: 12.11.2010
Сообщений: 808
28.12.2011, 14:02     Нужен простой пример бинарного поиска #1
Всем доброго времени суток. Кто может привести какой нибудь простенький пример бинарного поиска (будем считать что отсортированный массив уже есть)?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.12.2011, 14:02     Нужен простой пример бинарного поиска
Посмотрите здесь:

Реализовать алгоритм бинарного поиска с рекурсией C++
C++ Дерево бинарного поиска
Распечатка бинарного дерева поиска C++
Создание бинарного дерева поиска C++
C++ Реализация бинарного дерева поиска
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
28.12.2011, 14:09     Нужен простой пример бинарного поиска #2
Цитата Сообщение от DrSMERTb Посмотреть сообщение
Всем доброго времени суток. Кто может привести какой нибудь простенький пример бинарного поиска (будем считать что отсортированный массив уже есть)?
А просто погуглить - никак? Дофига в сети примеров.
DrSMERTb
 Аватар для DrSMERTb
59 / 35 / 4
Регистрация: 12.11.2010
Сообщений: 808
28.12.2011, 14:10  [ТС]     Нужен простой пример бинарного поиска #3
Не писал бы сюда если б не искал до этого. Посмотрел примеры понять не понял, так поэтому сюда и отписал.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 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, значит выходим из поиска, и возвращаем позицию.
DrSMERTb
 Аватар для DrSMERTb
59 / 35 / 4
Регистрация: 12.11.2010
Сообщений: 808
28.12.2011, 14:15  [ТС]     Нужен простой пример бинарного поиска #5
Ну это я понимаю, а как это будет в программе выглядеть?
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
28.12.2011, 14:16     Нужен простой пример бинарного поиска #6
Wikipedia
DrSMERTb
 Аватар для DrSMERTb
59 / 35 / 4
Регистрация: 12.11.2010
Сообщений: 808
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';
}
Только посмотрите пожалуйста на что он ругается.
Ватадот
 Аватар для Ватадот
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 );
    }
}
DrSMERTb
 Аватар для DrSMERTb
59 / 35 / 4
Регистрация: 12.11.2010
Сообщений: 808
28.12.2011, 15:46  [ТС]     Нужен простой пример бинарного поиска #9
А можете исходник целиком выложить?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.07.2014, 23:26     Нужен простой пример бинарного поиска
Еще ссылки по теме:

C++ Итератор дерева бинарного поиска
Нужен совет по алгоритму приближенного бинарного поиска C++
Реализация бинарного поиска C++

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

Или воспользуйтесь поиском по форуму:
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);
}
Yandex
Объявления
07.07.2014, 23:26     Нужен простой пример бинарного поиска
Ответ Создать тему
Опции темы

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