Программирование на языке С - Бинарный поиск

 

2.3.2. Бинарный поиск

Для упорядоченных линейных списков существуют более эффективные алгоритмы поиска, хотя и для таких списков применим последовательный поиск. Бинарный поиск состоит в том, что ключ 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); }