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实现二分查找算法

: » JavaScript实现二分查找算法

原创文章,作者:carmelaweatherly,如若转载,请注明出处:https://blog.ytso.com/251293.html

(0)
上一篇 2022年5月2日
下一篇 2022年5月2日

相关推荐

发表回复

登录后才能评论