Бинарный поиск — классический алгоритм. На вход алгоритм принимает отсортированный массив чисел и число для поиска. На выходе — индекс этого числа в массиве.
Алгоритмически это выглядит так:
- Запоминаем левую L и правую R границы массива (индексы, а не значения)
- Берем индекс M посередине между L и R
- Если значение массива по индексу M меньше нужного — L меняем на M, если больше — R меняем на M
- Возвращаемся на шаг 2
Таким образом мы на каждом шаге алгоритма сужаем область поиска в 2 раза. Этот алгоритм имеет сложность O(log(n)).
В теории все просто, но на практике возникают проблемы.
Приведу сразу свою реализацию, а потом разберем все проблемы.
Распространенная ошибка реализации — переполнение типа при вычислении середины интервала. Именно поэтому середина вычисляется так
Еще одна проблема — выход из алгоритма. Нужно правильно обрабатывать ситуацию, когда интервал поиска свелся к двум соседним индексам. Я для наглядности вместо хитрых операций с индексами вынес эту ситуацию в отдельный блок кода
Так же можно добавить дополнительную оптимизацию для ситуации, когда value заведомо слишком маленькое или большое. Будут такие проверки в начале метода:
Я ищу элемент х в отсортированном массиве. Он сравнивает хх или диапазон массива равен нулю. Я получаю ошибку сегментации, где я ошибся, я не смог найти мой код ниже
Я компилирую в GCC Complier.
Решение
Ваш рекурсивный поиск должен иметь возвращаемое значение на каждом пути, в противном случае его результаты не определены.
Рекурсивная функция работает точно так же, как и другие функции — если она утверждает, что возвращает значение, она должна это сделать. Он не просто автоматически возвращает результат завершающего рекурсивного вызова.
Ваш компилятор должен был предупредить вас об этом — если это не так, включите больше предупреждений.
Если это произошло, и вам было все равно, начните прислушиваться к предупреждениям.
Другие решения
Ниже функция имеет проблемы:
Когда вы вызываете эту функцию рекурсивно, вы должны вернуть значение как показано ниже
Если вы не вернетесь из некоторых путей кода функции, которая возвращает, код ведет себя не определено .
Как примечания стороны
- если вы собираетесь использовать этот код для очень больших массивов, (low + high) может переполниться, поэтому используйте
- Чтобы ваш компилятор предупреждал вас об этой компиляции с -Wall
вариант. - возврате -1 В случае ошибки не очень хорошая идея, если массив может содержать как положительные, так и отрицательные числа. Вы можете вернуть индекс массива, если найден и -1 если ошибка или устройство какое-то другое not found механизм.
Доброго времени суток! Не находит элемент в массиве. Подскажите, что не так? Я сам предполагаю, что все дело в return 0, но если меняю на значение 1, тогда он находит элементы, которых в массиве нет. В общем, сломал голову уже как корректно выйти из рекурсии, если конечно же все дело в этом.
Спасибо за внимание.
4 ответа 4
Готовый код под пунктами 1 и 2. Не принимайте под "чистую монету" : протестируйте. 🙂
Ваш код очень трудно понять, и в нём много недочётов. Сейчас мы постараемся это исправить и вместе с этим решить вашу проблему, но перед этим условимся, что вы корректно реализовали функцию sort 🙂
Начнём с bisearch . Поскольку функция рекурсивная, то было бы здорово при ваших условиях что-то возвращать + уберём "страшноватые" else if — конструкции,хоть они и были задуманы для выявления факта успешного завершения поиска :
Теперь нужно добавить ключевое условие сравнения :
Если ,в итоге, значение найдётся, то "раскрутим" стек и с нулём вернёмся в main , а иначе, рано или поздно, выполнится условие max , что скажет о провальном поиске. Думаю, что функция может выглядеть таким образом :
Теперь обсудим main . Первое, что "бросилось" в глаза — это следующее :
Что вам мешает сравнить возвращаемое значение функции с нулём? Вы на этом и ‘попались’ 🙂
if (x) — это эквивалент if (x != 0) , поэтому у вас программа запустится только при провале поиска, что нам не нужно, поэтому можно написать либо
Как вариант, функция может быть оформлена так :
Немного ‘побочины’ :
- Объявление midpoint находится в этом месте, чтобы не выполняться лишний раз (если, конечно, вы не используете ansi — стандарт при компиляции);
- Ограничение в виде size_t было сделано ради вашей же безопасности, потому что ни min , ни max (а значит и midpoint ) не могут быть по смыслу отрицательными значениями;
- Ещё , по-хорошему, надо добавить проверку на пустоту массива, но с этим вы уже сами справитесь. Только не добавляйте внутрь рекурсивной функции : сделайте это вне ёё, например, обвернув в другую функцию, а то при валидном массиве проверка на пустоту будет лишним действием. Там же и сделайте проверку на то, были ли действительно введены беззнаковые числа для min и max . (принимаем искомое значение, массив, int-ы, проверяем массив, проверяем min и max , а при успехе впускаем в функцию)
size_t я впихнул по двум причинам, одна из которых описана выше, а ,во-вторых, не будет излишнего преобразования типов (sizeof(der)/sizeof(der[0]) даст как раз size_t , что является беззнаковым целочисленным типом данных).
UPD: замените лучше везде unsigned int на size_t в вашей работе, ибо это беззнаковый и платформонезависимый тип + деление sizeof ‘ов ,на самом деле, дают size_t . Здесь уже подправил
Загрузка...
