首页 » 技术分享 » 算法——二分法查找(binarySearch)

算法——二分法查找(binarySearch)

 

二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法。

二分法查找的思路如下:

(1)首先,从数组的中间元素开始搜索,如果该元素正好是目标元素,则搜索过程结束,否则执行下一步。

(2)如果目标元素大于/小于中间元素,则在数组大于/小于中间元素的那一半区域查找,然后重复步骤(1)的操作。

(3)如果某一步数组为空,则表示找不到目标元素。

二分法查找的时间复杂度O(logn)。

非递归算法:

function binarySearch(arr,key){
	var low=0; //数组最小索引值
	var high=arr.length-1; //数组最大索引值
	while(low<=high){
		var mid=Math.floor((low+high)/2);
		if(key==arr[mid]){
			return mid;
		}else if(key>arr[mid]){
			low=mid+1;
		}else{
			high=mid-1;
		}
	}
	return -1; //low>high的情况,这种情况下key的值大于arr中最大的元素值或者key的值小于arr中最小的元素值
}

结果测试:

递归算法:

function binarySearch(arr,low,high,key){
	if(low>high){return -1;}
	var mid=Math.floor((low+high)/2);
	if(key==arr[mid]){
		return mid;
	}else if(key<arr[mid]){
		high=mid-1;
		return binarySearch(arr,low,high,key);
	}else{
		low=mid+1;
		return binarySearch(arr,low,high,key);
	}
}

结果测试:

转载自原文链接, 如需删除请联系管理员。

原文链接:算法——二分法查找(binarySearch),转载请注明来源!

0