二分查找法

    今天在csdn上看到了这么一篇文章只有10%的程序员能正确写出二分查找法，我看了觉得挺有意思的，c入门的时候也写过这个小程序，不过很多年没碰它了，还真有点生疏，我是到wikipedia重新看了一遍才写了如下代码的。没有测试，不知道是否完全正确。采用递归，各位还有无其他更好的方法？

def search a,left,right,n	
		if(right < left)
			return "not found"
		end
	mid=left+((right-left)/2)
	if(a[mid]>n)
		 search(a,left,mid-1,n)
	elsif a[mid]<n
		 search(a,mid+1,right,n)
	else
	   mid
	end
end

def binary_search(a,target)
	search(a,0,a.size-1,target)
end


a=[1,2,3,45,4,5,6,7,7,8,23]
 a.sort!
p binary_search(a,9)

评论

4 楼 googya 2010-08-06  

xiaobian 写道

<script>
	/**
	* binarySearch
	* 二分查找法
	* dest 要查找的对象
	*/
	Array.prototype.binarySearch =function(dest){
		var low = 0;
		var high = this.length - 1;
		
		while(low <=high){
			var middle = (low + high) >> 1;
	
			if(dest == this[middle]){
				return middle;
			}else if(dest < this[middle]){
				high = middle - 1;
			}else if(dest > this[middle]){
				low = middle + 1;
			}
		}
		return -1;
	}
	var oArr = new Array();
	for (var i=0;i<100 ;i++ )
	{
		oArr[i] = i + 1;
	}
	alert(oArr);
	alert(oArr.binarySearch(100));
</script>

js版本的也很容易懂哈

3 楼 xiaobian 2010-08-05  

<script>
	/**
	* binarySearch
	* 二分查找法
	* dest 要查找的对象
	*/
	Array.prototype.binarySearch =function(dest){
		var low = 0;
		var high = this.length - 1;
		
		while(low <=high){
			var middle = (low + high) >> 1;
	
			if(dest == this[middle]){
				return middle;
			}else if(dest < this[middle]){
				high = middle - 1;
			}else if(dest > this[middle]){
				low = middle + 1;
			}
		}
		return -1;
	}
	var oArr = new Array();
	for (var i=0;i<100 ;i++ )
	{
		oArr[i] = i + 1;
	}
	alert(oArr);
	alert(oArr.binarySearch(100));
</script>

2 楼 xiaobian 2010-08-05  

<script>
/**
* binarySearch
* 二分查找法
* dest 要查找的对象
*/
Array.prototype.binarySearch =function(dest){
var low = 0;
var high = this.length - 1;

while(low <=high){
var middle = (low + high) >> 1;

if(dest == this[middle]){
return middle;
}else if(dest < this[middle]){
high = middle - 1;
}else if(dest > this[middle]){
low = middle + 1;
}
}
return -1;
}
var oArr = new Array();
for (var i=0;i<100 ;i++ )
{
oArr[i] = i + 1;
}
alert(oArr);
alert(oArr.binarySearch(100));
</script>

1 楼 googya 2010-04-26  

这种写法受C C++ Java的影响太大了。