1

Доброго времени суток! Не находит элемент в массиве. Подскажите, что не так? Я сам предполагаю, что все дело в return 0, но если меняю на значение 1, тогда он находит элементы, которых в массиве нет. В общем, сломал голову уже как корректно выйти из рекурсии, если конечно же все дело в этом.

int main(int argc, char* argv[])
{
    int der[] = {1, 2,5 ,3 ,7, 5, 7, 10, 56, 10, 4};
    int s = (sizeof(der)/sizeof(der[0]));
    sort(der, s);
    for(int i = 0; i< s; i++)
        printf("%d ", der[i]);
    printf("\n");
    if (bisearch(10,  der, 0, s))
        printf("\n10 is found\n");
    return 1;
}

int bisearch(int val, int* array, int min, int max)
{
    int midpoint = (min+max)/2;
    if (max<min)
       return -1;
    if (array[midpoint] > val)
       bisearch(val, array, min, midpoint-1);
    else if (array[midpoint] < val)
       bisearch(val, array, midpoint+1, max);
    else
       return 1;
    return 0;
}

Спасибо за внимание.

5
  • пробуйте return -1
    – Demon __
    14 апр 2018 в 19:15
  • 1
    Ну разве можно что-то бинарно искать в неотсортированном массиве?...
    – Harry
    14 апр 2018 в 19:16
  • выше в основной функции, указана функция sort(). я код этой функции в вопросе упустил, поскольку она у меня работает корректно. В общем массив отсортирован. 14 апр 2018 в 19:19
  • тогда он утверждает, что нашел элемент, которого по факту нету в массиве. 14 апр 2018 в 19:26
  • А, да, пардон... не заметил.
    – Harry
    14 апр 2018 в 19:39

4 ответа 4

1

Готовый код под пунктами 1 и 2. Не принимайте под "чистую монету" : протестируйте. :)

Ваш код очень трудно понять, и в нём много недочётов. Сейчас мы постараемся это исправить и вместе с этим решить вашу проблему, но перед этим условимся, что вы корректно реализовали функцию sort :)

Начнём с bisearch. Поскольку функция рекурсивная, то было бы здорово при ваших условиях что-то возвращать + уберём "страшноватые" else if - конструкции,хоть они и были задуманы для выявления факта успешного завершения поиска :

if ( max < min ) return -1;
if ( array[midpoint] > val ) return bisearch( val, array, min, midpoint - 1 );
if ( array[midpoint] < val ) return bisearch( val, array, midpoint + 1, max );

Теперь нужно добавить ключевое условие сравнения :

if ( val == array[midpoint] ) return 0;

Если ,в итоге, значение найдётся, то "раскрутим" стек и с нулём вернёмся в main, а иначе, рано или поздно, выполнится условие max < min, что скажет о провальном поиске. Думаю, что функция может выглядеть таким образом :

1

int bisearch(int val, int* array, size_t min, size_t max)
{
    if ( max < min ) return -1;
    size_t midpoint = ( min + max ) / 2;  
    if ( array[midpoint] > val ) return bisearch(val, array, min, midpoint - 1 );
    if ( array[midpoint] < val ) return bisearch(val, array, midpoint + 1, max);
    if ( val == array[midpoint] ) return 0;
    return -1;
}

Теперь обсудим main. Первое, что "бросилось" в глаза - это следующее :

if (bisearch(10, der, 0, s))

Что вам мешает сравнить возвращаемое значение функции с нулём? Вы на этом и 'попались' :)

if (x) - это эквивалент if (x != 0), поэтому у вас программа запустится только при провале поиска, что нам не нужно, поэтому можно написать либо

if (0 == bisearch(10, der, 0, s))  

,либо

if (!bisearch(10, der, 0, s))

Как вариант, функция может быть оформлена так :

2

int main(int argc, char* argv[])
{
    int der[] = {1, 2, 5, 3, 7, 5, 7, 10, 56, 10, 4}; /*1 2 3 4 5 5 7 7 10 10 56*/
    size_t s = ( sizeof(der) / sizeof(der[0]) );
    sort( der, s );
    if ( 0 == bisearch(10, der, 0U, s) ) printf("10 was found\n");
    else printf("10 wasn't found\n");
    return 0;
}

Немного 'побочины' :

Для bisearch:

  1. Объявление midpoint находится в этом месте, чтобы не выполняться лишний раз (если, конечно, вы не используете ansi - стандарт при компиляции);
  2. Ограничение в виде size_t было сделано ради вашей же безопасности, потому что ни min, ни max (а значит и midpoint) не могут быть по смыслу отрицательными значениями;
  3. Ещё , по-хорошему, надо добавить проверку на пустоту массива, но с этим вы уже сами справитесь. Только не добавляйте внутрь рекурсивной функции : сделайте это вне ёё, например, обвернув в другую функцию, а то при валидном массиве проверка на пустоту будет лишним действием. Там же и сделайте проверку на то, были ли действительно введены беззнаковые числа для min и max. (принимаем искомое значение, массив, int-ы, проверяем массив, проверяем min и max, а при успехе впускаем в функцию)

для main:

size_tя впихнул по двум причинам, одна из которых описана выше, а ,во-вторых, не будет излишнего преобразования типов (sizeof(der)/sizeof(der[0]) даст как раз size_t, что является беззнаковым целочисленным типом данных).

UPD: замените лучше везде unsigned intна size_t в вашей работе, ибо это беззнаковый и платформонезависимый тип + деление sizeof'ов ,на самом деле, дают size_t. Здесь уже подправил

6
  • Спасибо вам большое за ваше разъяснение, очень информативно и полезно. Но ваш пример выдает ту же ошибку, как и у другого коллеги, что писал свой пост выше Ошибка: control may reach end of non-void function [-Werror, -Wreturn-type]. Система Linux, компилятор clang. 15 апр 2018 в 19:14
  • @ОлегХасьянов, у меня 'gcc' и такого не возникает. Вполне вероятно, что в функции bisearch clang боится ничего в итоге не вернуть, поэтому в конце нужен гарантированный return. Исправил эту функцию. Clang 3.8.0 больше не ругается. 15 апр 2018 в 19:24
  • теперь все заработало, спасибо большое. Хотел бы еще у вас спросить по поводу конструкции if - else if. Чем она плоха и в каких случаях ее рекомендуется использовать, а в каких нет? 15 апр 2018 в 20:10
  • @ОлегХасьянов, это было лично моё мнение. Я отметил их "страшноватыми" лишь только потому, что таким образом нарушается удобочитаемость кода. На самом деле,огромный плюс "if-else-if" в том, что, если выполнится определённое условие, то соответствующий блок выполнится и дальнейших проверок больше не будет, а в случае последовательных "if" условия пойдут проверяться дальше, НО поскольку в моём случае к каждому условию есть действие "return" при успешной проверке, то разницы нет. 15 апр 2018 в 20:57
  • 1
    Спасибо вам большое за ваше время и терпение :) ваши размышления очень полезны! 16 апр 2018 в 2:40
1

При вызове нужно корректно указывать последний индекс диапазона
Результаты рекурсивных вызовов нужно использовать, как уже сказали

int main()
{   int der[] = {1, 2, 3 ,3 ,5, 5, 7, 5, 10, 10, 56};
    int s = (sizeof(der)/sizeof(der[0]));
    for(int i = 0; i< s; i++)
        printf("%d ", der[i]);

    for (int v = 9; v<11; v++)
    {
       if (bisearch(v,  der, 0, s - 1))
          printf("\nvalue %d is found\n", v);
       else
          printf("\nvalue %d is Not found\n", v);
    }
    return 1;
}


int bisearch(int val, int* array, int min, int max)
{
    if (max<min)
       return 0;
    int midpoint = (min+max)/2;
    if (array[midpoint] > val)
       return bisearch(val, array, min, midpoint-1);
    else if (array[midpoint] < val)
       return bisearch(val, array, midpoint+1, max);
    else
       return 1;
}

 1 2 3 3 5 5 7 5 10 10 56
 value 9 is Not found
 value 10 is found
1
  • выдает ошибку: control may reach end of non-void function [-Werror, -Wreturn-type] По этой причине я указывал return 0, поэтому дело не в диапозоне, это я все так же перепроверял, перепоправлял. Система Linux, компилятор clang 15 апр 2018 в 16:25
0

Я нашел одно из решений. Правда, интуитивно мне кажеться это через-чур некрасивым кодом, если у кого есть более красивое решение, я буду только рад увидеть. Вот решение моей проблемы спустя пару дней головоломок: Объявляем глобальную переменную int r = 0; И в функции bisearch пишем:

int bisearch(int val, int* array, int min, int max)
{
    int midpoint = (min+max)/2;
    if(array[midpoint] > val) {
        if(max >= min) bisearch(val, array, min, midpoint - 1);
        else r = 0; }
    if(array[midpoint] < val) {
        if(max >= min) bisearch(val, array, midpoint + 1, max);
        else r = 0; }
    if(array[midpoint] == val) r = 1;

    if(max<min) r = 0;
    return r;
}
0

Мне кажется, в таких задачах лучше возвращать индекс найденного элемента (он будет в диапазоне от 0 до n (где n это размер массива)).
Если ключ не найден, то возвращаем -1.

Тогда, навскидку (на компе не проверял):

int bisearch (int k, int *a, int left, int n) {
  if (n <= left)
    return -1;
  int mid = (left + n) / 2;
  if (a[mid] == k)
    return mid;
  if (a[mid] < k)
    return bisearch(k, a, mid + 1, n);
  return bisearch(k, a, left, mid);
}
3
  • Это тоже хорошая мысль, только если искать не существующий элемент массива, он напишет, если я конечно же в main() все верно написал, что элемент найден, но я немного позволил себе изменить ваш код для более корректного решения поставленной задачи: в bisearch() возвращать при найденом элементе return a[mid], а в основной функции main() прописать такие условия, что int n = 5; if(n == bisearch(n, a, 0, size) printf("was found") else ("wasn't); Спасибо ваше внимание. 16 апр 2018 в 3:27
  • А не проще запомнить результат поиска (индекс) и сравнить с -1? if ((index == bisearch(n, a, 0, size)) != -1) printf("was found") else ("wasn't); Если же, задача в самом деле только определить, найден или нет, то лучше сделать "обертку" bool is_found (int k, int *a, int left, int n) { return bisearch(k, a, left, n) != -1; }
    – avp
    16 апр 2018 в 18:35
  • Да, второй вариант с "оберткой" то, что надо по условии задачи, вернуть логическую истину или же ложь. Спасибо большое. 16 апр 2018 в 19:14

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.