I'm thinking of a number between 1 and 127 inclusive.
It is 55, but I'm not telling you that.

You know the   so you work out     so      so you can
  possible      the mid-point       I       eliminate
  range is        and guess       reply     anything
------------   ---------------   -------   ----------
  1 to 127        
                     64
                                 too big
                                              >= 64
  1 to 63
                     32
                                too small
                                              <= 32
 33 to 63
                     48
                                too small
                                              <= 48
 49 to 63
                     56
                                 too big
                                              >= 56
 49 to 55
                     52
                                too small
                                              <= 52
 53 to 55
                     54
                                too small
                                              <= 54
 55 to 55
                     55
                                 correct

That is always the optimum strategy. Guess the mid point.
The number of possibilities is halved at each step.

     size of range      max number of guesses needed                        
    ---------------    ------------------------------
              1               1
              3               2
              7               3
             15               4
             31               5
             63               6
            127               7
            255               8
            511               9
          1,023              10
          2,047              11
          4,095              12
          8,191              13
         16,383              14
         32,767              15
         65,535              16
        131,071              17
        262,143              18
        524,287              19
      1,048,575              20
      2,097,151              21
      4,194,303              22
      8,388,607              23
     16,777,215              24
     33,554,431              25
     67,108,863              26
    134,217,727              27
    268,435,455              28
    536,870,911              29
  1,073,741,823              30

With just 30 guesses, you can search through over a billion
possibilities.



#include <library.h>

string words [] = { "a", "ant", "bat", "cat", "dog", "elephant", "frog",
                    "hat", "goat", "ingot", "jelly", "kangaroo", "limp",
                    "mongoose", "nose", "oaf", "penguin", "quilt", "rat",
                    "sealion", "taxi", "unicorn", "vole", "wombat", "x",
                    "yetti", "zanzibar" };
const int entries = 27;

     // that's not quite a billion, but my fingers are tired


int find(const string s,
         const int min_pos,
         const int max_pos)
{
  if (min_pos > max_pos)
    return -1;
  const int guess = (min_pos + max_pos) / 2;
  if (words[guess] == s)
    return guess;
  if (words[guess] > s)
    return find(s, min_pos, guess - 1);
  else
    return find(s, guess + 1, max_pos);
}


void main()
{ while (true)

  { print("search for: ");
    const string w = read_string();

    const int p = find(w, 0, entries - 1);

    if (p == -1)
      print("not found\n\n");
    else
    { print("it is at position ");
      print(p);
      print("\n\n"); } } }