定义一个二分查找法的函数

所谓二分查找法，是一种在有序数组里快速查找元素的方法。通过不断搜索中间值来定位元素在这个有序数组里的位置；

今天用Javascript写出这个查找方法的逻辑，并封装成函数

定义一个函数，名为halfSearch，接受的参数是 升序数组 和 查找的元素。它将会返回元素的索引

function halfSearch(arr,targetItem){
}

定义两个变量，分别是搜索的起始位置和结束位置，然后对比起始位置与结束位置最中间位置的元素

function halfSearch(arr,targetItem){
	var fromLeft=0;
	var toRight=arr.length;
	var find=(toRight-fromLeft)/2 + fromLeft;
	if(arr[find]==targetItem){
		return find;
	}
}

当得到的数小了的时候把左指针放数组中间，重新查找。

反过来，数大了就把右指针放数组中间。

function halfSearch(arr,targetItem){
	var fromLeft=0;
	var toRight=arr.length-1;
	while(arr[find]!=targetItem){
		var find=Math.floor( (toRight-fromLeft)/2 + fromLeft )
		if(arr[find] 
BUG：有些时候while循环会卡住。 
原因：find是一个数除以二得来的，可能会冒出一个0.5
 
解决：添加Math.floor取整
 
function halfSearch(arr,targetItem){
	var fromLeft=0;
	var toRight=arr.length-1;
	while(arr[find]!=targetItem){
		var find=Math.floor( (toRight-fromLeft)/2 + fromLeft )
		if(arr[find] 
BUG：当没有找到元素时while循环也会卡住 
解决：添加判断，当左指针和右指针相等或者差值为1就返回-1
 
function halfSearch(arr,targetItem){
	var fromLeft=0;
	var toRight=arr.length-1;
	while(arr[find]!=targetItem){
		var find=Math.floor( (toRight-fromLeft)/2 + fromLeft )
		if(arr[find] 
BUG：如果数在最右边，无法搜索到值 
 
修复：toRight的初始值从length-1修改成length
 
function halfSearch(arr,targetItem){
	var fromLeft=0;
	var toRight=arr.length;
	while(arr[find]!=targetItem){
		var find=Math.floor( (toRight-fromLeft)/2 + fromLeft )
		if(arr[find]targetItem){
			//猜大了
			toRight=find;
		}
		if(toRight-fromLeft<=1&&arr[toRight]!=targetItem&&arr[fromLeft]!=targetItem){
			return -1
		}
	}
	return find
}
 
简单测试