ОСТОРОЖНО МОШЕННИКИ! В последнее время в соиальных сетях учстились случаи педложения помощи в написании прогамм от лиц, прикрвающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в псторонних группах ВК. Для связи с нами используйте исключительно эти контакт: vscoderu@yandex.ru, https://vk.com/vscode


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


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

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

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

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


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

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

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

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

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

 

 

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

 

4.7/5 - (13 голосов)



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

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

Ваш адрес email не будет опубликован.