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

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

Войти
Регистрация
Восстановить пароль
 
NRX
12 / 12 / 4
Регистрация: 22.09.2015
Сообщений: 120
#1

Поиздеавться над бинарным поиском - C++

12.06.2016, 21:03. Просмотров 156. Ответов 6
Метки нет (Все метки)

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

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
int double_search(int i, int size, int right, int left, int *var)
{
    int position = left + (right - left) / 2;
    if (var[position] == i) return position;
    if (left == right || right < 0) return -std::numeric_limits<int>::max();
    if (var[position] > i)
    {
        right = position - 1;
        double_search(i, size, right, left, var);
    }
    else
    {
        left = position +1;
        double_search(i, size, right, left, var);
    }
}
 
int double_search(int i, int size, int *var)
{
    int right = size - 1, left = 0;
    
    return double_search(i, size, right, left, var);
    
}
(Если искомого числа нет то возвращает наименьший из возможных int)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dastan4ik
61 / 61 / 31
Регистрация: 18.10.2014
Сообщений: 186
Завершенные тесты: 2
12.06.2016, 21:23     Поиздеавться над бинарным поиском #2
C++
1
2
3
int position = left + (right - left) / 2;
я думаю  что будет
int position = (left + right)/ 2;
NRX
12 / 12 / 4
Регистрация: 22.09.2015
Сообщений: 120
12.06.2016, 21:29  [ТС]     Поиздеавться над бинарным поиском #3
будет переполнение при очень огромных массивах (вычитал в интернете, сам не проверял)
Dastan4ik
61 / 61 / 31
Регистрация: 18.10.2014
Сообщений: 186
Завершенные тесты: 2
12.06.2016, 21:37     Поиздеавться над бинарным поиском #4
Да я просто не учел приоритеты операций.

Добавлено через 3 минуты
Еще попробуй
C++
1
  if (left >= right || right < 0) return -std::numeric_limits<int>::max();
Renji
1753 / 1180 / 275
Регистрация: 05.06.2014
Сообщений: 3,399
12.06.2016, 21:41     Поиздеавться над бинарным поиском #5
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Эм... На кой вам там рекурсия? В которой, кстати, return перед вложенными вызовами потерян.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int double_search(int value, int size, const int *var)
{
    const int*const startVar=var;
    while(size>1)
    {
        const int pos=size/2;
        if(var[pos]<=value)
        {
            var+=pos;
            size-=pos;
        }else
            size=pos;
    }
    return *var==value?var-startVar:std::numeric_limits<int>::min();
}
NRX
12 / 12 / 4
Регистрация: 22.09.2015
Сообщений: 120
12.06.2016, 21:50  [ТС]     Поиздеавться над бинарным поиском #6
Цитата Сообщение от Renji Посмотреть сообщение
Эм... На кой вам там рекурсия? В которой, кстати, return перед вложенными вызовами потерян.
А. ну да
Требование преподавателя, чтобы алгоритм был рекурсивным
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.06.2016, 22:49     Поиздеавться над бинарным поиском
Еще ссылки по теме:

Поиск бинарным методом C++
C++ Работа с бинарным файлом
Работа с бинарным файлом C++
Сортировка бинарным деревом C++

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

Или воспользуйтесь поиском по форуму:
Геомеханик
529 / 336 / 257
Регистрация: 26.06.2015
Сообщений: 769
12.06.2016, 22:49     Поиздеавться над бинарным поиском #7
Сообщение было отмечено автором темы, экспертом или модератором как ответ
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
#include <iostream>
 
int bfind(const int a[], int l, int r, int v){
    if(l >= r)
        return -1;
 
    int i, m = l + (r - l)/2;
    if(v < a[m])
        i = bfind(a, l, m, v);
    else if(v > a[m])
        i = bfind(a, m + 1, r, v);
    else
        i = m;
    return i;
}
 
int main(void){
    int a[] = { -512, 0,1,2,3,4,5,6,7,8,9, 1000 };
    int n   = sizeof(a)/sizeof(a[0]);
 
    for(int i = -3000; i < 3000; ++i){
        if(bfind(a, 0, n, i) != -1)
            std::cout << "find: " << i << std::endl;
    }
    return 0;
}
Yandex
Объявления
12.06.2016, 22:49     Поиздеавться над бинарным поиском
Ответ Создать тему
Опции темы

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