JavaScript实现二分查找算法

公告：“业余草”微信公众号提供免费CSDN下载服务(只下Java资源)，关注业余草微信公众号，添加作者微信：xttblog2，发送下载链接帮助你免费下载！
本博客日IP超过2000，PV 3000 左右，急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包，请加博主新的微信号：xttblog2，之前的微信号好友位已满，备注：返现
受密码保护的文章请关注“业余草”公众号，回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽，请关注文末小程序

腾讯云】1核2G5M轻量应用服务器50元首年，高性价比，助您轻松上云

一直以来大家都认为 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）！可加作者微信号：xttblog2。备注：“1”，添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注！后续有精彩内容会第一时间发给您！原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系！

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