JavaScript实现二分查找算法

一直以来大家都认为 JavaScript 更偏向于前端，导致了网上关于 JavaScript 算法方面的内容不是很多。因此本文便借助 JavaScript 来实现数组的二分查找算法。

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

二分查找是一个基础的算法，也是面试中常考的一个知识点。二分查找就是将查找的键和子数组的中间键作比较，如果被查找的键小于中间键，就在左子数组继续查找；如果大于中间键，就在右子数组中查找，否则中间键就是要找的元素。

基本思路

数组中间位置对应的值与需要查找的值比较，如果两者相等，则查找成功；否则利用中间位置记录将数组分成前、后两个子数组，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子数组，否则进一步查找后一子数组，然后依递归。

下面是 JavaScript 实现二分查找算法的实现代码：

/**
 * [binarySearch 二分查找]
 * @param  {[type]} value      [查找元素]
 * @param  {[type]} arr        [数组]
 * @param  {[type]} startIndex [开始索引]
 * @param  {[type]} endIndex   [结束索引]
 * @return {[type]}            [返回查找元素的索引]
 */
function binarySearch(value,arr,startIndex,endIndex) {
	if(!value|| !(arr instanceof Array)) return;
	//：www.xttblog.com
	var len        = arr.length,
		startIndex = typeof startIndex === "number" ? startIndex : 0,
		endIndex   = typeof endIndex   === "number" ? endIndex   : len-1,
		midIndex   = Math.floor((startIndex + endIndex) / 2),
		midval     = arr[midIndex];
	//：www.xttblog.com
	if(startIndex > endIndex) return ;
	//：www.xttblog.com
	if(midval === value){
		return midIndex;
	}else if (midval > value) {
		return binarySearch(value, arr, startIndex, midIndex - 1);
	}else {
		return binarySearch(value, arr, midIndex + 1, endIndex);
	}
}
console.log(binarySearch(3,[1,2,3,4,5,6,7]));//2

以上就是关于 JavaScript 实现二分查找算法的实现。

： » JavaScript实现二分查找算法