时间:2021-05-26
二分查找的前提为:数组、有序。逻辑为:优先和数组的中间元素比较,如果等于中间元素,则直接返回。如果不等于则取半继续查找。
/** * 二分查找,递归实现。 * @param target * @param arr * @param start * @param end * @returns {*} */function binarySearch(target,arr,start,end) { var start = start || 0; var end = end || arr.length-1; var mid = parseInt(start+(end-start)/2); if(target==arr[mid]){ return mid; }else if(target>arr[mid]){ return binarySearch(target,arr,mid+1,end); }else{ return binarySearch(target,arr,start,mid-1); } return -1;}/** * 有序的二分查找,返回-1或存在的数组下标。不使用递归实现。 * @param target * @param arr * @returns {*} */function binarySearch(target,arr) { var start = 0; var end = arr.length-1; while (start<=end){ var mid = parseInt(start+(end-start)/2); if(target==arr[mid]){ return mid; }else if(target>arr[mid]){ start = mid+1; }else{ end = mid-1; } } return -1;}写完有序,自然而然的想到了无序的情况如何使用二分查找呢?马上想到先使用快排分组,分好组再二分。代码如下:
/** * 无序的二分查找。返回true/false * @param target * @param arr * @returns {boolean} */function binarySearch(target,arr) { while (arr.length>0){ //使用快速排序。以mid为中心划分大小,左边小,右边大。 var left = []; var right = []; //选择第一个元素作为基准元素(基准元素可以为任意一个元素) var pivot = arr[0]; //由于取了第一个元素,所以从第二个元素开始循环 for(var i=1;i<arr.length;i++){ var item = arr[i]; //大于基准的放右边,小于基准的放左边 item>pivot ? right.push(item) : left.push(item); } //得到经过排序的新数组 if(target==pivot){ return true; }else if(target>pivot){ arr = right; }else{ arr = left; } } return false;}写完用快速排序实现的无序二分查找,仔细想了一下该算法的时间复杂度,发现还不如直接一个for循环来得快
以上所述是小编给大家介绍的JavaScript实现二分查找实例代码,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对网站的支持!
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例为大家分享了Java实现二分查找的变种,供大家参考,具体内容如下普通二分查找:先回顾一下普通的二分查找注意:二分查找有这样一个问题:当数组中数有重复时,
本文实例讲述了JavaScript使用二分查找算法在数组中查找数据的方法。分享给大家供大家参考。具体分析如下:二分查找又称折半查找,优点是比较次数少,查找速度快
整理文档,搜刮出一个JavaScript用二分法查找数据的实例代码,顺便做个笔记//二分法查数据vararr=[41,43,45,53,44,95,23];va
这篇文章主要介绍了Java二分查找算法实现代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下二分查找:两
本文实例为大家分享了java实现二分法查找出数组重复数字的具体代码,供大家参考,具体内容如下packageoffer;/***二分查找的思想来找到数组中重复的数