Двоичный поиск на Си

В этой статье поговорим о поиске. Рассмотрим двоичный (бинарный) поиск. Будет представлен его алгоритм, а также пример программы, реализующей поиск элемента в массиве. Разработку будем вести на языке программирования Си.

Перед поиском исходная последовательность должна быть обязательно отсортирована!

Итак, идея двоичного поиска состоит в следующем: искомый элемент сравнивается со средним элементом последовательности. Если значение аргумента поиска меньше среднего элемента, то исходной последовательностью считается массив элементов от 1 до N/2, если значение аргумента поиска больше среднего элемента, то исходной считаем последовательность от N/2 до N. Далее, для новой последовательности этот процесс повторяется. Продолжаем деление пополам интервала поиска до тех пор, пока не будет найден искомый элемент или длина интервала поиска не станет равна единице.

Приведем реализацию алгоритма на языке Си. Функция int binarysearch(int a, int mass[], int n) в качестве аргументов принимает: искомый элемент, указатель на массив элементов и число элементов в этом массиве. В случае успешного поиска binarysearch возвращает позицию искомого элемента в массиве, если аргумент поиска отсутствует в последовательности элементов, то функция возвратит -1.

Теперь приведем пример консольной программы, которая производит двоичный поиск в массиве элементов длиной N. Для сортировки последовательности используется метод сортировки вставками.

Демонстрация работы программы представлена на скриншоте ниже:

Двоичный поиск на Си - vscode.ru

Если вы желаете скачать исходник программы, то нажмите на кнопку:

Скачать исходник

 

 

Посмотрите также, как реализуется алгоритм двоичного (бинарного) поиска на С++.

 

Двоичный поиск на Си
4 (80%) 4 votes

Поделиться в соц. сетях:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">