算法练习(87):热还是冷(1.4.34)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 热还是冷

题目

1.4.34 热还是冷。你的目标是猜出 1 到 N 之间的一个秘密的整数。每次猜完一个整数后，你会知道你的猜测距离该秘密整数是否相等（如果是则游戏结束）。如果不相等，你会知道你的猜测相比上一次猜测距离秘密整数是比较热（接近），还是比较冷（远离）。设计一个算法在 ~2lgN 之内找到这个秘密整数，然后设计一个算法在 ~1lgN 之内找到这个秘密整数。

---

1.4.34 Hot or cold. Your goal is to guess a secret integer between 1 and N. You repeatedly guess integers between 1 and N. After each guess you learn if your guess equals the secret integer (and the game stops). Otherwise, you learn if the guess is hotter (closer to) or colder (farther from) the secret number than your previous guess. Design an algorithm that finds the secret number in at most ~2lg N guesses. Then design an algorithm that finds the secret number in at most ~ 1 lgN guesses.

分析

这道题是2010年IOI(International Olympiadin Informatics国际信息学奥林匹克竞赛)的竞赛题。
有对IOI不熟悉的，我这里再做个简单的介绍：

国际信息学奥林匹克竞赛（International Olympiad in Informatics，IOI），是面向中学生的一年一度的信息学科竞赛。第一届国际信息学奥林匹克竞赛于1989年在保加利亚的布拉维茨举行。
这项竞赛包含两天的计算机程序设计，解决算法问题。选手以个人为单位，每个国家最多可选派4名选手参加（2014年有来自83个国家和地区的311名选手参赛 ）。参赛选手从各国相应计算机竞赛中选拔。
IOI的采用C，C++，Pascal作为参赛的三种程序语言。
2016年的IOI采用Python，Pascal，C，C++，Java五种语言作为参赛语言。

Stack Overflow上有这道题，我们大概看一下：

Hot and Cold Binary Search Game