JavaScript实现二分查找实例代码

二分查找的前提为：数组、有序。逻辑为：优先和数组的中间元素比较，如果等于中间元素，则直接返回。如果不等于则取半继续查找。

/**
 * 二分查找，递归实现。
 * @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实现二分查找实例代码，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对网站的支持！

# javascript二分查找 # JavaScript中二分查找的例题详解 # JavaScript数据结构与算法之检索算法示例【二分查找法、计算重复次数】 # JavaScript折半查找（二分查找）算法原理与实现方法示例 # JS二分查找算法详解 # js基本算法:冒泡排序 # 二分查找的简单实例 # js实现的二分查找算法实例 # javascript实现二分查找法实现代码 # JS实现二分查找的示例代码 # 递归 # 第一个 # 写完 # 小编 # 在此 # 第二个 # 给大家 # 想了 # 不等于 # 自然而然 # 所述 # 如何使用 # 给我留言 # 感谢大家 # 疑问请 # 有任何 # 来得快 # arr # target # param

返回目录在线咨询

上一篇：台州普通网站制作人才招聘,台州有哪些团购网站？
下一篇：服务器绑定网站时遇到“域名解析失败”怎么办？

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

全网整合营销服务商

JavaScript实现二分查找实例代码

您的项目需求