Вот, например, хороший ответ.

This rule means that if the header uses a type - such as 'FILE *' or 'size_t' - then it must ensure that the appropriate other header ( or for example) should be included. A corollary, often forgotten, is that the header should not include any other header that is not needed by the user of the package in order to use the package. The header should be minimal, in other words.

Вкратце: включений в заголовке должно быть как можно меньше, при этом в нём должны быть включены все заголовки, необходимые для беспрепятственной работы кода, в нём описанного.

В вашем случае, если vector используется исключительно в реализации и в описании blackbox'a никак себя не проявляет, включать его нужно в .cpp

Поняли правильно, это обыкновенный двоичный поиск. Обычно он реализуется рекурсивно, можете посмотреть исполнение, например, в Википедии.
Написать лучше тоже можно - с переносами строк и пробелами выглядеть будет гораздо приятнее.

P.s. У вас 8 проходов цикла.

upd. Если предположить, что каждый вопрос (неважно какой) - это попытка, то можно ограничиться только семью вопросами. Например, так:

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    setlocale(LC_ALL, "Russian");

    int min = 1, max = 100;
    cout << "Загадайте число от " << min << " до " << max << ".\n";

    int guess = (min + max) / 2, count = (int) ceil(std::log2(max - min));
    for (int i = 0; i < count; ++i)
    {
        cout << "Загаданное число меньше или равно " << guess << "? (y/n)\n";   // fixed

        char ans;
        cin >> ans;
        if (ans == 'y')
        {
            max = guess;
        }
        else
        {
            min = guess + 1;    // fixed
        }
        guess = (min + max) / 2;

        if (max == min)    // fixed
        {
            cout << "Вы загадали число \"" << guess << "\".\n";
            system("PAUSE");
            return 0;
        }
    }

    cout << "Жулик!\n";
    system("PAUSE");
    return 0;
}

Каких-то специальных рекомендаций для Qt лично я не видел. Есть общие концепции вроде MVC, MVP и проч.
Прочитайте, например, про model-view в документации того же Qt. Разделите по тому же принципу движок (model) и интерфейс (view). Добавьте во View ссылку на модель и ловите сигналы.