Готовый код под пунктами 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
:
- Объявление
midpoint
находится в этом месте, чтобы не выполняться лишний раз (если, конечно, вы не используете ansi - стандарт при компиляции);
- Ограничение в виде
size_t
было сделано ради вашей же безопасности, потому что ни min
, ни max
(а значит и midpoint
) не могут быть по смыслу отрицательными значениями;
- Ещё , по-хорошему, надо добавить проверку на пустоту массива, но с этим вы уже сами справитесь. Только не добавляйте внутрь рекурсивной функции : сделайте это вне ёё, например, обвернув в другую функцию, а то при валидном массиве проверка на пустоту будет лишним действием. Там же и сделайте проверку на то, были ли действительно введены беззнаковые числа для
min
и max
. (принимаем искомое значение, массив, int-ы, проверяем массив, проверяем min
и max
, а при успехе впускаем в функцию)
для main
:
size_t
я впихнул по двум причинам, одна из которых описана выше, а ,во-вторых, не будет излишнего преобразования типов (sizeof(der)/sizeof(der[0])
даст как раз size_t
, что является беззнаковым целочисленным типом данных).
UPD: замените лучше везде unsigned int
на size_t
в вашей работе, ибо это беззнаковый и платформонезависимый тип + деление sizeof
'ов ,на самом деле, дают size_t
. Здесь уже подправил