“猜手机号游戏”的源码分析：二分查找+面向对象
很多朋友体验了“给哥三十五次机会，哥就能猜中你的手机号”，反馈还不错。有些明眼的朋友，一眼就看出来所用的算法。D瓜哥表示很佩服。另外有一些朋友也问所使用的算法，D瓜哥今天就把源代码和算法全部揭晓。
其实，这个代码很简单。不过也有三个看点：二分查找算法、面向对象编程和对数的计算。下面我们一一讲解。
二分查找算法
基本原理是二分查找算法。首先，我们先简要介绍一下“二分查找算法”。
二分查找又称折半查找，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下时间复杂度是O(log2n)。由此看出，二分查找的优点很明显：比较次数少，查找速度快，,平均性能好；不过，也有一些缺点。其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
二分查找运行时，会首先，假设列表中元素是按升序排列，将列表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将列表分成前、后两个子列表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子列表，否则进一步查找后一子列表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子列表不存在为止，此时查找不成功。
基本原理是这样。不过，我在处理的时候没有列表，直接拿(min+max)/2来显示“猜测结果”。说到这里了，再多说一句。其实是用(min+max)/2的计算有Bug，可能会产生溢出问题。更好的计算方法是：min+(max-min)/2；或是(min+max)>>>1。
面向对象编程
在Javascript中进行“面向对象编程”一直是我提倡的实践。这样，能良好的封装代码，提高代码的可重用性、可读性以及可维护性。以前的文章里面，也多次提到要整几篇文章，讲解一下“面向对象编程”。只是因为各种原因，一直未能兑现。抱歉，这篇也只能讲解个大概。不过，我保证，这方面的内容，一定会写出来的。
扯淡为目的的文章不是好文章。转入正题。因为，我这篇文章只要是分析“猜手机号游戏”的源代码，所以就直接拿源代码讲解面向对象了。
在对象封装方面，我使用了“构造函数模式”。具体代码如下：
/**
* numberScope 需要猜测的数字范围
*/
function GuessNumber(numberScope){
this._maxNumber = -1; // 猜测范围中，最大的数
this._minNumber = 0; // 猜测范围中，最小的数
this._nowNumber = -1; // 目前猜测出来的数
this._count = 0; // 需要猜测的次数
this._times = 0; // 猜测的次数
this._result = 0; // 猜测结果
this._complete = false; // 猜测是否完成
this._success = false; // 猜测是否成功。
this.setNumberScope(numberScope); //设置猜数范围，这里默认从0开始.
}
这样的话，就可以使用new 来创建对象，同时一些必要的值，也可以在new的时候，通过构造函数的参数传进去。创建对象的代码如下：
var guess = new GuessNumber(100);
大家也许注意到了，上面构造函数中的有一行方法调用的代码，如下：
this.setNumberScope(numberScope); //设置猜数范围，这里默认从0开始.
也许大家会奇怪，这个方法是从哪里来的呢？
在对象上添加方法，我使用了“原型模式”。JavaScript中的原型prototype，最大的特点就是“共享”。由于，函数只需要“一套”，所有对象都可以共用一套函数。所以，这种共享特性非常适合用来定义函数。代码如下：
GuessNumber.prototype = {
constructor: GuessNumber,
//设置数字范围
setNumberScope: function(numberScope){
if(numberScope < 0){
alert("数字范围不能小于0！");
return;
}
this._numberScope = numberScope;
this.start(this._minNumber, numberScope);
},
//开始游戏，初始化一些必要的数据。主要是为方便重新设定最小值。所以将最小值作为第一个参数
start: function(minNumber, maxNumber) {
var inMinNum = this._minNumber;
var inMaxNum = this._numberScope;
this._minNumber = -1;
this._maxNumber = 1;
// 当minNumber为0时，需要特殊处理一下。
var minNumberStr = minNumber + "";
if (minNumberStr != "") {
inMinNum = minNumber;
}
if (maxNumber) {
inMaxNum = maxNumber;
this._numberScope = maxNumber;
}
this._complete = false;
this._success = false;
this._times = 0;
this.changeFields(inMaxNum, inMinNum);
this.setCount();
},
// 计算所需猜测的次数
setCount: function() {
this._count = Math.ceil(Math.log(this._maxNumber - this._minNumber) / Math.log(2)) + 1;
},
//猜测的数字太小，调大数字
toLarger: function(){
this.changeFields(this._maxNumber, this._nowNumber);
},
//猜测的数字太大，调小数字
toSmaller: function(){
this.changeFields(this._nowNumber, this._minNumber);
},
//计算数字大小，修改相应值
changeFields: function(maxNumber, minNumber){
if(maxNumber <= minNumber || maxNumber == this._minNumber + 1) {
if(!this._complete) {
this.complete();
}
return;
}
if(this._maxNumber !== maxNumber) {
this._maxNumber = maxNumber;
}
if(this._minNumber !== minNumber) {
this._minNumber = minNumber;
}
this._nowNumber = Math.round((this._maxNumber + this._minNumber) / 2);
this._times ++;
},
……
}
注意，这个的第二行。使用这种语法是非常方便。但是，却从本质上改变了GuessNumber.prototype。致使constructor不再指向GuessNumber函数。这样做是特意将其设置成GuessNumber，以使其能访问到合适的值。
这样，最主要的代码都已经完成。剩下的工作就是调用相应的方法就行。更加详细、完整的代码将在下面展示。
对数的计算
这里讲解一些数学上的知识。不喜欢的，可以忽略过去。
大家也许好奇，为啥我能准确估算出“猜测次数”。其实，我们可以反过来考虑，比我们需要找一个比n（n为正整数）大的数。我们可以从1开始向后数，数到n，再到n+1就可以了。但是这种效率有点低，我们都学过乘方，我们可以从1开始，反复乘以2，假如需要乘以x个2，即2x >= n,这样效率就会很高。再反过来，负负得正，在一个1到2x范围内，我们每次砍去一半，最多砍到第x次，就肯定能找出这个数过来。那么，这个x怎么求呢？
其实，这就要用到数学的对数知识。用数学公式来求解的话，就是x = log2n。在Javascript中，数学相关的计算方法都在Math中。查一下Math的API，我们就会发现只有一个Math.log(n)方法，而且这个方法求的是以10为底n的对数。我们需要求的是以2为底n的对数，不符合我们的需求。肿么办？这时，数学知识再次向我们展示了她的无穷魅力。
可能我们在高中学过对数，了解对数的变换公式。其中一个就能帮助我们：logab = logmb / logma。所以，我们的问题就迎刃而解：x = log10n / log102。在数学中，log10n可以简写成logn，所以 x = log10n / log102 = logn / log2。不过，这样计算出来的结果还会有小数点，这是我们只需要来个“向上取整”就可以了。具体代码如下：
// 计算所需猜测的次数
setCount: function() {
this._count = Math.ceil(Math.log(this._maxNumber - this._minNumber) / Math.log(2)) + 1; //加1，确保次数肯定用。
},
完整代码实现
下面把完整代码贴出来，方便大家阅读。
/**
* numberScope 需要猜测的数字范围
*/
function GuessNumber(numberScope){
this._maxNumber = -1; // 猜测范围中，最大的数
this._minNumber = 0; // 猜测范围中，最小的数
this._nowNumber = -1; // 目前猜测出来的数
this._count = 0; // 需要猜测的次数
this._times = 0; // 猜测的次数
this._result = 0; // 猜测结果
this._complete = false; // 猜测是否完成
this._success = false; // 猜测是否成功。
this.setNumberScope(numberScope); //设置猜数范围，这里默认从0开始.
}
GuessNumber.prototype = {
constructor: GuessNumber,
//设置数字范围
setNumberScope: function(numberScope){
if(numberScope < 0){
alert("数字范围不能小于0！");
return;
}
this._numberScope = numberScope;
this.start(this._minNumber, numberScope);
},
//根据数字长度，设定数字访问
setNumberScopeWithNumberLength: function(numLength){
this.setNumberScope(Math.pow(10, numLength));
},
// 设置最小的数
setMinNumber: function(minNumber) {
this.start(minNumber);
},
//开始游戏，初始化一些必要的数据。主要是为方便重新设定最小值。所以将最小值作为第一个参数
start: function(minNumber, maxNumber) {
var inMinNum = this._minNumber;
var inMaxNum = this._numberScope;
this._minNumber = -1;
this._maxNumber = 1;
// 当minNumber为0时，需要特殊处理一下。
var minNumberStr = minNumber + "";
if (minNumberStr != "") {
inMinNum = minNumber;
}
if (maxNumber) {
inMaxNum = maxNumber;
this._numberScope = maxNumber;
}
this._complete = false;
this._success = false;
this._times = 0;
this.changeFields(inMaxNum, inMinNum);
this.setCount();
},
// 计算所需猜测的次数
setCount: function() {
this._count = Math.ceil(Math.log(this._maxNumber - this._minNumber) / Math.log(2)) + 1;
},
// 获取总的猜测次数
getCount: function() {
if (this._count === 0) {
this.setCount();
}
return this._count;
},
//猜测的数字太小，调大数字
toLarger: function(){
this.changeFields(this._maxNumber, this._nowNumber);
},
//猜测的数字太大，调小数字
toSmaller: function(){
this.changeFields(this._nowNumber, this._minNumber);
},
//计算数字大小，修改相应值
changeFields: function(maxNumber, minNumber){
if(maxNumber <= minNumber || maxNumber == this._minNumber + 1) {
if(!this._complete) {
this.complete();
}
return;
}
if(this._maxNumber !== maxNumber) {
this._maxNumber = maxNumber;
}
if(this._minNumber !== minNumber) {
this._minNumber = minNumber;
}
this._nowNumber = Math.round((this._maxNumber + this._minNumber) / 2);
this._times ++;
},
//提前完成猜数
complete: function() {
this._complete = true;
if (this._maxNumber === this._minNumber) {
this._success = true;
this._result = this._maxNumber;
} else if (this._maxNumber < this._minNumber) {
this._success = false;
this._result = "Sorry! I failed.";
} else {
this._success = true;
this._result = this._nowNumber = Math.round((this._maxNumber + this._minNumber) / 2);
if (this._nowNumber == this._minNumber + 1) {
this._nowNumber = this._minNumber;
}
}
},
//获取结果
getResult: function() {
if(!this._success) {
return "Sorrry! I failed.";
}
return this._result;
},
// 获取猜测的数
getGuess: function() {
if(this._nowNumber == this._minNumber) {
return Math.round((this._maxNumber + this._minNumber) / 2);
}
return this._nowNumber;
},
//获取猜测次数
getTimes: function() {
if(this._times === 0) {
this.start();
}
return this._times;
}
}
剩下的，就是创建对象，事件绑定。另外，GuessNumber主程序输出的是数字，还要根据实际情况进行格式化。这个不多说，具体代码如下：
$(document).ready(function(){
//格式化显示结果
function formatResult(num, type) {
if (type == 1) {
var tmp = new Date(num * 1000 * 3600 * 24);
return tmp.getFullYear()+"年"+(tmp.getMonth()+1)+"月"+tmp.getDate()+"日";
} else {
var numStr = num + "";
var strLeng = numStr.length;
var result = "";
for(var i = strLeng; i >= 0; i -= 4) {
var startIndex = i-4 > 0 ? i-4 : 0;
result = numStr.substring(startIndex, i) + result;
if(i > 4) {
result = "-" + result;
}
}
return result;
}
}
function showResult() {
if(guess._complete){
// 为了简化处理结果，把结果展示暂时写到这里。
if(guess._success) {
alert("您猜测的结果是：" + formatResult(guess.getGuess(), type));
} else {
alert("猜测失败。要不，咱试试其他的？");
}
return;
}
document.getElementById("showNumber").value = formatResult(guess.getGuess(), type);
document.getElementById("showTimes").innerHTML = guess.getTimes();
document.getElementById("showCount").innerHTML = guess.getCount();
}
var guess = new GuessNumber(100);
// 定义个猜数范围数组
var scopeArr = [{min: 0, max: 100, tip: ""}, // 小试牛刀
{min: Math.round(new Date(0).getTime() / (1000*3600*24)),
max: Math.round(new Date().getTime() / (1000*3600*24)),
tip: ""}, // 猜猜生日
{min:Math.pow(10, 10), max: 2*Math.pow(10, 10),
tip: ""} // 猜猜手机号
];
var type = 0; //1 代表日期；其余代表数字
guess.start(scopeArr[type].min, scopeArr[type].max);
showResult();
$("#guessType").change(function(){
type = $(this).val();
guess.start(scopeArr[type].min, scopeArr[type].max);
showResult();
});
//alert("Scope："+guess._numberScope+"，Max："+guess._maxNumber+"，Min："+guess._minNumber+"，Now："+guess._nowNumber+"，Count："+guess._count);
$("#maxButton").click(function(){
guess.toSmaller();
showResult();
});
$("#minButton").click(function(){
guess.toLarger();
showResult();
});
$("#initButton").click(function(){
guess.start(scopeArr[type].min, scopeArr[type].max);
showResult();
});
});
原来不想贴HTML的代码了，不过想想，既然是完整的，就都贴出来吧。
<div style="background: #E6FAE6; padding-left: 15px; border: 1px dashed #E0E0E0;">
<p>开始猜：最多需要<span id="showCount"></span>次</p>
<p> 选择一个类型：
<select id="guessType">
<option value ="0">小试牛刀-猜一百以内的正整数</option>
<option value ="1">猜猜你的生日</option>
<option value="2">信不信，我能猜出你的手机号</option>
</select></p>
<p> <input type="text" value="" size="24" maxlength="50" readonly="true" id="showNumber" style="font-size:150%;"></p>
<p> <input type="button" value="出错就重来" id="initButton"> <input name="tooMax" type="button" value="太大" id="maxButton" style="font-size:140%;"> 第<span id="showTimes"></span>次 <input name="tooMin" type="button" value="太小" id="minButton" style="font-size:140%;"></p>
</div>
所有代码都贴出来了，从这些代码中也可以看出来，猜测的时候没有和后台进行通信。所以，大家可以放心大胆的试。
稍后，我会把代码发布到Github上，请大家关注我的Github账号：D瓜哥。
参考资料：
原文链接：https://wordpress.diguage.com/archives/80.html
版权声明：非特殊声明均为本站原创作品，转载时请注明作者和原文链接。
特别感谢扣扣网友“谢安”！
在原文中，我错把logab = logmb / logma写成了 logab = logma / logmb。感谢“谢安”的指正！有问题，请留言，D瓜哥会及时改正的。
Math.log(n),这个方法是以Math.E为底数,不是10为底数;
Math.log(Math.E); // 1
Math.log(10); //2.30+
学习了
搜面向对象 搜过来的
纠结了好久 格式化日期下面的 else 是在干嘛
原来是手机号相关的
写的好巧 都塞到了一起