Реализация бинарного поиска гадания

Question

Я пытаюсь написать программу, в которой компьютер пытается угадать номер, который пользователь выбирает (1 - 100). У меня большая часть выписанной программы, а также генератор случайных чисел. Единственное, что мне нужно сейчас - это способ реализовать алгоритм бинарного поиска в моей программе на основе пользовательских входов HIGH или LOW. Я читал некоторые о бинарном алгоритме поиска, но я не уверен, как его использовать в моей программе. Может ли кто-нибудь указать мне в правильном направлении?

Линии 34 и 42 имеют пробел, где должна быть функция. Вот где я хотел бы ввести какое-то уравнение, которое реализует алгоритм бинарного поиска в моей программе.

Ниже мой код, как сейчас:

#include <iostream> 
#include <ctime>//A user stated that using this piece of code would make a true randomization process. 
#include <cstdlib> 
#include <windows.h> 
using namespace std; 

int main() 
{ 
    int highLow; 
    int yesNo; 
    int ranNum; 
    srand(time(0)); 


    ranNum = rand() % 100 + 1; 

    cout << "Please think of a number between 1-100. I'm going to try to guess it.\n"; 
    _sleep(3000); 

    cout << "I'm going to make a guess. Is it "<< ranNum <<" (1 for yes and 2 for no)?\n"; 
    cin >> yesNo; 


    while (yesNo == 2) 
     { 
      cout << "Please tell me if my guess was higher or lower than your number\n"; 
      cout << "by inputting 3 for HIGHER and 4 for LOWER.\n"; 
      cin >> highLow; 

      if (highLow == 3) 
       { 
        cout << "Okay, so my guess was higher than your number. Let me try again.\n"; 
        _sleep (1500); 
        cout << "Was your number " << <<"? If yes, input 1. If not, input 2.\n";// I would like to find a way to implement the 
       //binary search algorithm in this line of code. 
        cin >> yesNo; 
       } 
      if (highLow == 4) 
       { 
        cout << "Okay, so my guess was lower than your number. Let me try again.\n"; 
        _sleep (1500); 
        cout << "Was your number " << <<"? If yes, input 1. If not, input 2.\n";// I would like to find a way to implement the 
       //binary search algorithm in this line of code. 
        cin >> yesNo; 
       } 
     } 
     if (yesNo == 1) 
     { 
      cout << "My guess was correct!\n"; 
     } 
} 

Answer 1

Держите два целых числа bottom и top. loop invariant - это номер пользователя [внизу; Вверх].

Теперь мы хотим свести к минимуму количество догадок. Для этого мы хотим выбросить как можно больше из [дна; top] множество чисел (если мы предположили ошибочно).

Чтобы выбросить как можно больше, мы всегда можем угадать floor((bottom + top)/2).

Чтобы реализовать это, мы можем отрегулировать bottom или top согласно нашей новой информации. Если он был слишком высоким, мы установили top в guess - 1. Если он был слишком низким, мы установили bottom в guess + 1.

С этой стратегией в худшем случае вы должны угадать только floor(log2(100)) = 6 раз. С 1000 номерами на выбор - достаточно 9 догадок.

Предположим, что искомое число равно 2. Итак, мы предполагаем: 50 (высокий), 25 (высокий), 12 (высокий), 6 (высокий), 3 (высокий), 1 (низкий). Мы не догадываемся/спрашиваем пользователя за 2, так как мы уже на 100% уверены, что это 2.