JavaScript数据结构与算法之检索算法示例【二分查找法、计算重复次数】
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了JavaScript数据结构与算法之检索算法示例【二分查找法、计算重复次数】,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2765字,纯文字阅读大概需要4分钟。
内容图文
本文实例讲述了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代码运行工具:http://tools.jb51.net/code/HtmlJsRun测试上述代码,可得如下运行结果:
更多关于JavaScript相关内容感兴趣的读者可查看本站专题:《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。
内容总结
以上是互联网集市为您收集整理的JavaScript数据结构与算法之检索算法示例【二分查找法、计算重复次数】全部内容,希望文章能够帮你解决JavaScript数据结构与算法之检索算法示例【二分查找法、计算重复次数】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。