Бинарный поиск
Для упорядоченных линейных списков существуют более эффективные алгоритмы поиска, хотя и
для таких списков применим последовательный поиск. Бинарный поиск состоит в том, что
ключ V сравнивается со средним элементом списка. Если эти значения окажутся равными, то
искомый элемент найден, в противном случае поиск продолжается в одной из половин списка.
Нахождение элемента бинарным поиском осуществляется очень быстро. Max бинарного поиска
равен log2(N), и при одинаковой частоте использования каждого элемента Avg бинарного
поиска равен log2(N). Недостаток бинарного поиска заключается в необходимости
последовательного хранения списка, что усложняет операции добавления и исключения
элементов.
Пусть, например, во входном потоке задано 101 число, К1,К2,...,К100, V - элементы списка
и ключ. Известно, что список упорядочен по возрастанию, и элемент V в списке имеется.
Составим программу для ввода данных и осуществления бинарного поиска ключа V в списке
К1,К2,...,К100.
/* Бинарный поиск */
#include
main()
{
int k[100],v,i,j,m;
for (i=0;i<100;i++) scanf("%d",&k[i]);
scanf("%d",&v); i="0;" j="100;" m="50;"
while (k[m]!="v)" { if (k[m] < v) i+="m;"
else j="m-i;" m="(i+j)/2;" }
printf("%d %d",v,m);
}