欢迎来到 jackNEss'窝窝
I like simple mind

javascript算法优化——二分查找法

2011年11月20日

二分查找法

说到javscript 性能优化中的算法优化,有一个我觉得有必要了解的就是 二分查找法。

二分查找法

二分查找法,也称为折半查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。

实现原理

将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如果x<a[n/2],则我们只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列)。如果x &rt;a[n/2],则我们只要在数组a的右半部继续搜索x。

应用实例

//javascript document
function showNumber(num){
	if(num == 1){
		return "Ace";
	}
	
	else if(num == 2){
		return "Deuce";
	}
	
	else if(num == 3){
		return "Trey";
	}
	
	else if(num == 4){
		return "Cater";
	}
	
	else if(num == 5){
		return "Cinque";
	}
	
	else if(num == 6){
		return "Sice";
	}
	
	else if(num == 7){
		return "Seven";
	}
	
	else if(num == 8){
		return "Eight";
	}
	
	else if(num == 9){
		return "Nine";
	}
	
	else if(num == 10){
		return "Ten";
	}
	
	else if(num == 11){
		return "Jack";
	}
	
	else if(num == 12){
		return "Queen";
	}
	
	else if(num == 13){
		return "King";
	}
	
}

上面的这个函数是 根据输入的数字 返回该数字对于扑克的英文叫法(为什么是扑克?最终幻想零式的错,俺现在中毒已深了,嗷嗷…)。

在这个 if-else 表达式中,条件语句最多要判断 13 次,假设 num 的值 在 1 – 13 之间均匀分布的话,那么这种写法就会增加平均运行时间。

为了最小化条件判断的次数,代码可以重写为一系列嵌套的 if-else 语句:

//javascript document
function showNumber(num){
	if(num < 7){
		if(num < 4){
			if(num == 1){
				return "Ace";
			}
			else if(num == 2){
				return "Deuce";
			}
			else if(num == 3){
				return "Trey";
			}
		}
		else{
			if(num == 4){
				return "Cater";
			}
			else if(num == 5){
				return "Cinque";
			}
			else if(num == 6){
				return "Sice";
			}
			
		}
		
	}
	else{
		if( num < 10){
			if(num == 7){
				return "Seven";
			}
			else if(num == 8){
				return "Eight";
			}
			else if(num == 9){
				return "Nine";
			}
			
		}
		else{
			if(num == 10){
				return "Ten";
			}
			else if(num == 11){
				return "Jack";
			}
			else if(num == 12){
				return "Queen";
			}
			else if(num == 13){
				return "King";
			}
			
		}
		
	}
	
}

重写后 的 if-else 语句每次到达正确分支最多经过 6 次条件判断,这就是一个 运用二分查找法优化的实例,通过这种方法进行算法优化,就以上这个为例,代码运行平均时间大约是前面例子的一半。

适用范围

二分查找法非常适用于有多个值域需要测试的时候,不过,如果是离散值的话,那么 switch 语句通常更为适合

分类javascript
阅读 3,553
  • 评论加载中...

标签云

分类目录

最新留言

  • 评论加载中...

与我联系

如有疑问or建议可通过以下方式跟我取得联系.

Q Q:373435871
Email:jackness1208@gmail.com
© Copyright 2011 - 2014 jackNEss.org All Rights Reserved 粤ICP备14065612号
首页 | 关于我 | 网站地图 | RSS