JavaScript数据结构与算法之检索算法示例【二分查
网络编程 2021-07-04 15:50www.168986.cn编程入门
这篇文章主要介绍了JavaScript数据结构与算法之检索算法,结合实例形式分析了二分查找法、计算重复次数相关算法原理与使用技巧,需要的朋友可以参考下
本文实例讲述了JavaScript数据结构与算法之检索算法。分享给大家供大家参考,具体如下
javascript数据结构与算法---检索算法(二分查找法、计算重复次数)
/只需要查找元素是否存在数组,可以先将数组排序,再使用二分查找法/ function qSort(arr){ if (arr.length == 0) { return []; } var left = [];//存储小于基准值 var right = [];//存储大于基准值 var pivot = arr[0]; for (var i = 1; i < arr.length; i++) { if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return qSort(left).concat(pivot, qSort(right));//递归 } /二分查找法,基本原理如下 将数组的第一个位置设置为下边界(0).将数组的一个元素所在的位置设置为上边界(数组的长度减1)。 若下边界等于或小于上边界,则做如下操作 (1).将中点设置为(上边界加上下边界) 除以2. (2). 如果中点的元素小于查询的值,则将下边界设置为中点元素所在下标加1. (3). 如果中点的元素大于查询的值,则将上边界设置为中点元素所在下标减1. (4). 否则中点元素即为要查找 的数据,可以进行返回。/ function binSearch(arr,data) { var lowerBound = 0; var upperBound = arr.length - 1; while(lowerBound <= upperBound) { var mid = Math.floor((upperBound + lowerBound)/2); if(arr[mid] < data) { lowerBound = mid + 1; }else if(arr[mid] > data) { upperBound = mid - 1; }else { return mid; } } return -1; } / 计算重复次数 当binSearch()函数找到某个值时,如果在数据集中还有其他相同的值出现,那么该函数会定位在类似值的附近。 换句话说,其他相同的值可能会出现已找到值的左边或右边。 如果在数据集中能找到这个值,那么这个函数将开始通过两个循环来统计这个值出现的次数。 第一个循环向下遍历数组,统计找到的值出现的次数,当下一个值与要查找的值不匹配时则停止计数。 第二个循环向上遍历数组,统计找到的值出现的次数,当下一个值与要查找的值不匹配时则停止计数。 / function count(arr, data) { var count = 0; var position = binSearch(arr, data); if (position > -1) { ++count; for (var i = position-1; i > 0; --i) { if (arr[i] == data) { ++count; } else { break; } } for (var i = position+1; i < arr.length; ++i) { if (arr[i] == data) { ++count; } else { break; } } } return count; } var nums = [90,43,49,15,23,2,70,23,20,95,69,23,29,26]; var list = qSort(nums); console.log(list); var findnum = 23; console.log("需要查找的数据为: " + findnum); var retVal = binSearch(list, findnum); if (retVal >= 0) { console.log( "找到 " + findnum + "的位置为 "+retVal); }else { console.log(" is not in array."); } console.log(findnum + "重复次数为"+count(list, findnum));
使用在线HTML/CSS/JavaScript代码运行工具:测试上述代码,可得如下运行结果
更多关于JavaScript相关内容感兴趣的读者可查看本站专题《》、《》、《》、《》、《》、《》及《》
希望本文所述对大家JavaScript程序设计有所帮助。
编程语言
- 甘肃哪有关键词排名优化购买方式有哪些
- 甘肃SEO如何做网站优化
- 河南seo关键词优化怎么做电话营销
- 北京SEO优化如何做QQ群营销
- 来宾百度关键词排名:提升您网站曝光率的关键
- 卢龙关键词优化:提升您网站排名的策略与技巧
- 山东网站优化的注意事项有哪些
- 四川整站优化怎样提升在搜索引擎中的排名
- 疏附整站优化:提升网站性能与用户体验的全新
- 海南seo主要做什么工作售后服务要做到哪些
- 荣昌百度网站优化:提升您网站的搜索引擎排名
- 河北seo网站排名关键词优化如何做SEO
- 江西优化关键词排名推广售后保障一般有哪些
- 古浪SEO优化:提升你的网站可见性
- 西藏网站排名优化怎么把网站排名在百度首页
- 如何提升阳东百度快照排名:详尽指南