решенный интерактивный поиск

#include <iostream>
using namespace std;

void bin( int a, int b, int l, int n)
{

  if (n-l==1)
  {
    if (a!=l)
    cout << "! " << l << endl;
    else cout << "! " << n << endl;
  }
  else
  {
    int i=(n-l)/2+1+l;
    int middle = 0;

     cout << "?" << " " << i << endl;
     cin >> middle;

     if (middle - a != i-1-l)
      {
       n=i-1;
       bin (a, middle, l, n);
      }
     else//проверяем вторую половину
     {
      if (b-middle!=i-1) //берем последний элемент первой половины как 0 следующей половины
       {
        l=i-1;
        bin (middle, b, l, n);
       }
     }
  }
}

int main()
{
 cout.flush();
 int n;
 cin >> n;

int elem_last=0, elem_0=0;

  cout << "?" << " " << 1 << endl;
  cin >> elem_0;

  cout << "?" << " " << n << endl;
  cin >> elem_last;

  bin(elem_0, elem_last, 0, n-1);
}