二分查找及其应用 By ElemenT今天，你今天，你ACAC了吗？了吗？NO!NO!YES!YES!请在这里输入您的标题刷题太无聊？我们玩游戏吧！相信大家都玩过猜数字的相信大家都玩过猜数字的游戏。两人游戏，游戏。两人游戏，A同学在心同学在心里默念一个整数里默念一个整数n（1=n=1000）。）。B同学猜同学猜n是多少。是多少。同时如果同时如果B没有猜对，没有猜对，A告诉告诉他这个数比默念的数高了还他这个数比默念的数高了还是低了。是低了。最坏情况下，最坏情况下，ElemenTElemenT也也不不用用超超过过十次可以猜出！十次可以猜出！最坏情况下需要多少次呢？看起来好厉害的样子其实并不是，下面将引入其实并不是，下面将引入“二二分搜索分搜索”的概念。的概念。如上述的游戏中，第一次应该如上述的游戏中，第一次应该取多少呢？取多少呢？500！很不巧并不是很不巧并不是500，而是一个比，而是一个比500大的数。大的数。虽然运气不好，但是虽然运气不好，但是B将区间的将区间的范围砍掉了一半！范围砍掉了一半！那么下一次那么下一次B该猜什么。该猜什么。大家已经发现，问题变成了501-1000501-10
