本系列博客習(xí)題來自《算法(第四版)》泳唠，算是本人的讀書筆記，如果有人在讀這本書的宙搬，歡迎大家多多交流笨腥。為了方便討論，本人新建了一個微信群(算法交流)害淤，想要加入的扇雕，請?zhí)砑游业奈⑿盘枺簔hujinhui207407 謝謝。另外窥摄，本人的個人博客 http://www.kyson.cn 也在不停的更新中，歡迎一起討論
知識點(diǎn)
- 熱還是冷
題目
1.4.34 熱還是冷础淤。你的目標(biāo)是猜出 1 到 N 之間的一個秘密的整數(shù)崭放。每次猜完一個整數(shù)后，你會知道你的猜測距離該秘密整數(shù)是否相等（如果是則游戲結(jié)束）鸽凶。如果不相等币砂，你會知道你的猜測相比上一次猜測距離秘密整數(shù)是比較熱（接近），還是比較冷（遠(yuǎn)離）玻侥。設(shè)計一個算法在 ~2lgN 之內(nèi)找到這個秘密整數(shù)决摧，然后設(shè)計一個算法在 ~1lgN 之內(nèi)找到這個秘密整數(shù)。
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國際信息學(xué)奧林匹克競賽)的競賽題。
有對IOI不熟悉的掌桩，我這里再做個簡單的介紹：
國際信息學(xué)奧林匹克競賽（International Olympiad in Informatics边锁，IOI），是面向中學(xué)生的一年一度的信息學(xué)科競賽波岛。第一屆國際信息學(xué)奧林匹克競賽于1989年在保加利亞的布拉維茨舉行茅坛。
這項(xiàng)競賽包含兩天的計算機(jī)程序設(shè)計，解決算法問題则拷。選手以個人為單位贡蓖，每個國家最多可選派4名選手參加（2014年有來自83個國家和地區(qū)的311名選手參賽 ）。參賽選手從各國相應(yīng)計算機(jī)競賽中選拔煌茬。
IOI的采用C斥铺，C++，Pascal作為參賽的三種程序語言坛善。
2016年的IOI采用Python仅父，Pascal，C浑吟，C++笙纤，Java五種語言作為參賽語言。
Stack Overflow上有這道題组力，我們大概看一下：
