Алгоритм нахождения числа за 2 ⁿ раз

      Алгоритм двоичного поиска исключает половину еще непроверенных элементов массива после каждого сравнения. Алгоритм определяет местоположение среднего элемента массива и сравнивает его с ключом поиска. Если они равны, то ключ поиска найден и выдается индекс этого элемента. В противном случае задача сокращается на половину элементов массива. Если ключ поиска меньше, чем средний элемент массива, то дальнейший поиск осуществляется в первой половине массива, а если больше, то во второй половине. Если ключ поиска не совпадает со средним элементом выбранного подмассива (части исходного массива), то алгоритм повторно применяется и сокращает область поиска до четверти исходного массива. Поиск продолжается до тех пор, пока ключ поиска не станет равным среднему элементу или пока оставшийся подмассив содержит хотя бы один элемент, не равный ключу поиска.
      В худшем случае двоичный поиск в массиве из 1024 элементов потребует только 10 сравнений. Повторяющееся деление 1024 на 2 (поскольку после каждого сравнения мы можем исключить половину элементов массива) дает 512, 256, 128, 64, 32, 16, 8, 4, 2 и 1. Число 1024 (210) делится на 2 только десять раз. Деление на 2 эквивалентно одному сравнению в алгоритме двоичного поиска. Массив из 1048576 (220) элементов требует для нахождения ключа поиска самое большее 20 сравнений. Массив из одного миллиарда элементов требует для нахождения ключа поиска максимум 30 сравнений. Это огромное увеличение эффективности по сравнению с линейным поиском, который в среднем требует числа сравнений, равного половине числа элементов в массиве. Для миллиарда элементов выигрыш равен разнице между 500 миллионами сравнений и 30 сравнениями! Максимальное количество сравнений, необходимое для двоичного поиска в любом отсортированном массиве, может быть определено как первый показатель степени, при возведении в который числа 2 будет превышено число элементов в массиве. Все вышесказаное реализовывается при помощи рекурсии).
      Сперва нужно поставить условие на то, что элемент равен ключу, в нашем случае ключ равен 1, т.к. нам нужно найти число, которое задумает пользователь, а разница между загаданым и предлагаемым числами должна быть не более 1. Переменные BEG и END - начачало диапазона, и конец диапазона соответственно.

  if (END-BEG==1)                            // odds in diapason
  {
    printf("Is your number %d Y/N : ",BEG);  // number - 1 ?
    char key=getch();
    if (key==(char)0x79) return BEG;         // YES
    else return END;                         // NO
  }		

      Теперь нужно реализовать вычисление середины диапазона, и проверку - входит ли это число в диапазон от BEG до Middle :

  Middle=(END+BEG)/2;                            // calculate middle diaposone
  printf("Your number to be in diapason %d - %d Y/N : ",BEG,Middle);
  key=getch();
  printf("\n");	

      И вот теперь нам нужно реализовать условие, если число входит в диапазон от BEG до Middle, то тогда нужно вызвать функцию расчета еще раз, а если не входит, тогда тоже вызвать эту функцию, но прибавить к Middle+1. Это нужно для того, чтобы сдвинуть диапазон на 1 вверх от последнего максимального значения, которое было. Проще всего это реализовать с помощью рекурсии. Функция которую будем вызывать называется - SearchBinary, она имеет два входных параметра : начало диапазона и конец диапазона.

  if (key==(char)0x79) SearchBinary(BEG,Middle); // number in diapason ? YES
  else SearchBinary(Middle,END+1);               // NO	

      Ниже приведен пример функции, которая ищет число загаданое пользователем. Программа написаная на языке "С++".

int SearchBinary(int BEG, int END)
{
  int key,Middle;
  if (END-BEG==1)                                // odds in diapason
  {
    printf("Is your number %d Y/N : ",BEG);      // number - 1 ?
    char key=getch();
    if (key==(char)0x79) return BEG;             // YES
    else return END;                             // NO
  }
  Middle=(END+BEG)/2;                            // calculate middle diaposone
  printf("Your number to be in diapason %d - %d Y/N : ",BEG,Middle);
  key=getch();
  printf("\n");
  if (key==(char)0x79) SearchBinary(BEG,Middle); // number in diapason ? YES
  else SearchBinary(Middle,END+1);               // NO	
} 		

      Готовый вариант программы сможете найти, щелкнув в навигационной панели ссылку Готовые программы.