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

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

Восстановить пароль Регистрация
 
NRX
 Аватар для NRX
11 / 11 / 3
Регистрация: 22.09.2015
Сообщений: 90
12.06.2016, 21:03     Поиздеавться над бинарным поиском #1
Вот у меня задание, написать алгоритм бинарного поиска числа в отсортированном по возрастанию массиве. Вот я написал. вроде бы все потестил. Но по закону подлости преподаватель находит бреши в программе. Пожалуйста поиздевайтесь над этой программой:

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)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.06.2016, 21:03     Поиздеавться над бинарным поиском
Посмотрите здесь:

C++ Помогите с бинарным файлом
C++ Баг с бинарным списком
задача с бинарным файлом C++
C++ Проблемы с бинарным файлом
C++ Поиск буквы бинарным поиском в тексте
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dastan4ik
60 / 60 / 31
Регистрация: 18.10.2014
Сообщений: 185
Завершенные тесты: 2
12.06.2016, 21:23     Поиздеавться над бинарным поиском #2
C++
1
2
3
int position = left + (right - left) / 2;
я думаю  что будет
int position = (left + right)/ 2;
NRX
 Аватар для NRX
11 / 11 / 3
Регистрация: 22.09.2015
Сообщений: 90
12.06.2016, 21:29  [ТС]     Поиздеавться над бинарным поиском #3
будет переполнение при очень огромных массивах (вычитал в интернете, сам не проверял)
Dastan4ik
60 / 60 / 31
Регистрация: 18.10.2014
Сообщений: 185
Завершенные тесты: 2
12.06.2016, 21:37     Поиздеавться над бинарным поиском #4
Да я просто не учел приоритеты операций.

Добавлено через 3 минуты
Еще попробуй
C++
1
  if (left >= right || right < 0) return -std::numeric_limits<int>::max();
Renji
1534 / 982 / 240
Регистрация: 05.06.2014
Сообщений: 2,958
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
 Аватар для NRX
11 / 11 / 3
Регистрация: 22.09.2015
Сообщений: 90
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++ Работа с бинарным файлом

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

Или воспользуйтесь поиском по форуму:
Геомеханик
 Аватар для Геомеханик
517 / 324 / 253
Регистрация: 26.06.2015
Сообщений: 738
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     Поиздеавться над бинарным поиском
Ответ Создать тему
Опции темы

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