JavaScript实现二分查找算法

HTML5 herman 1055浏览 0评论
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xttblog,发送下载链接帮助你免费下载!
本博客日IP超过1800,PV 2600 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog,之前的微信号好友位已满,备注:返现
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领

一直以来大家都认为 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 实现二分查找算法的实现。

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加QQ1群:135430763(2000人群已满),QQ2群:454796847(已满),QQ3群:187424846(已满)。QQ群进群密码:xttblog,想加微信群的朋友,之前的微信号好友已满,请加博主新的微信号:xttblog,备注:“xttblog”,添加博主微信拉你进群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作可添加助理微信进行沟通!

本文原文出处:业余草: » JavaScript实现二分查找算法