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