二分搜索的经典例题。我在这里踩了一个坑,幸好,让我发现了一个思维漏洞。
二分法中,在 range [bg, ed)
里搜索,每次 mid = bg + (ed - bg) / 2
。我起先对这种貌似多此一举的求中位方法不以为意,猜想可能是为了支持指针操作(不能把两个指针相加)。今天才发现原来还有确保对负数也成立的功能(如果是 mid = (bg + ed) / 2
的形式,会出现死循环)。
#include <iostream>
#include <string>
using namespace std;
int main() {
int bg = -1'000'000'000;
int ed = 1'000'000'001;
while (true) {
int mid = bg + (ed - bg) / 2;
cout << mid << endl;
string a;
cin >> a;
if (a == "big")
ed = mid;
else if (a == "small")
bg = mid + 1;
else
break;
}
}
C++ ostream 的
endl
本身就会刷新缓冲区,没有必要显式地调用os.flush()
。