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

赞 (0)

相关推荐

  • js基本算法:冒泡排序,二分查找的简单实例

    知识扩充: 时间复杂度:算法的时间复杂度是一个函数,描述了算法的运行时间.时间复杂度越低,效率越高. 自我理解:一个算法,运行了几次时间复杂度就为多少,如运行了n次,则时间复杂度为O(n). 1.冒泡排序 解析:1.比较相邻的两个元素,如果前一个比后一个大,则交换位置. 2.第一轮的时候最后一个元素应该是最大的一个. 3.按照步骤一的方法进行相邻两个元素的比较,这个时候由于最后一个元素已经是最大的了,所以最后一个元素不用比较. function sort(elements){ for(var i

  • JavaScript使用二分查找算法在数组中查找数据的方法

    本文实例讲述了JavaScript使用二分查找算法在数组中查找数据的方法.分享给大家供大家参考.具体分析如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表.首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一

  • js实现的二分查找算法实例

    本文实例讲述了js实现的二分查找算法.分享给大家供大家参考,具体如下: <!DOCTYPE html> <html> <head> <title>demo</title> <style type="text/css"> </style> <script type="text/javascript"> var binarySearch = function(array, s

  • javascript实现二分查找法实现代码

    一般二分都用到int[]型上.....在js中可能会更灵活的用到a-z上,或者用到拼音...或者用到...... 不过值得深思的一个问题是,如果为了实现对拼音之类的二分查找.而经过如下流程是否值得: 1.对拼音排序,貌似代码量不小吧. 2.然后再二分查找.这又需要识别拼音的大小,貌似也不算太小吧. 找到结果的速度快了,可是别人下你的js文件速度慢多了,呵呵,到底舍弃谁. 下面的代码甚至可以10亿条,一样会很快找到,可是用遍例的模式创建那个数组...所以还是别尝试了.只是给个思路,下次我再来发个j

  • JS二分查找算法详解

    二分法查找,也称折半查找,是一种在有序数组中查找特定元素的搜索算法.查找过程可以分为以下步骤: (1)首先,从有序数组的中间的元素开始搜索,如果该元素正好是目标元素(即要查找的元素),则搜索过程结束,否则进行下一步. (2)如果目标元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半区域查找,然后重复第一步的操作. (3)如果某一步数组为空,则表示找不到目标元素. 参考代码: // 非递归算法 function binary_search(arr, key) { var low = 0,

  • 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

  • JavaScript+CSS相册特效实例代码

    JavaScript+CSS相册特效实例代码

    嗯 就是这样一个例子,视频学到的一个特效,实际用处并不大,但是可以帮助理解JS语言和熟悉CSS3样式. 设计: 观察一张图片的变化,发现: 1.图片缩放(随机,并且不是同时运动) 1.从大到小 2.从小到大,透明度从1到0(在第一步运动完成后立马开始) 2.图片旋转(随机,并且不是同时运动的.需要在全部运动走完以后开始) 3. 因为每张图片是随机开始变换的,所以起始时间是不同的,这里可设置一个延迟器setTimeout,时间用random随机生成即可. 4. 中间需要用到自执行函数,因为setT

  • JavaScript判断微信浏览器实例代码

    先给大家说下我的项目需求:用户扫一扫二维码会产生一个链接,该链接会向后端发送个请求,返回一个 apk 的下载地址,用户点击下载按钮可以下载此 apk.然后就发生了问题,经过测试,发现用微信扫一扫打开的页面点击下载按钮下载不了 apk,后百度之,原来是微信内置浏览器屏蔽了下载链接,后面和需求方沟通,需求改为如果用户是用微信内置浏览器打开的,则提示用户换一个浏览器打开页面,否则下载不了 apk.那么该如何判断用户是否是用微信浏览器呢? 我们知道 js 可以通过 window.navigator.us

  • javascript数字验证的实例代码(推荐)

    javascript数字验证的实例代码(推荐)

    现在有一个需求如下图: 产品经理说Card Number只能让输入数字(中间的空格是格式自加的,也是用js实现的),有时候我脑海中出现了个声音,啥玩意,加个type=number不就行了,事实发现图样图森破了,先不说type=number后面会有个上下标(虽然用css可干掉),但是这个类型是支持科学输入法的,就是小数点和e这样的是可以输入的,于是乎只能用其他的方式了,后来想用检索到输入了非数字就干掉,但是这样还是能输入,想法被打回,于是乎最终采用了键盘输入控制的办法,其实很简单, 代码如下: v

  • ECHO.js 纯javascript轻量级延迟加载的实例代码

    ECHO.js 纯javascript轻量级延迟加载的实例代码

    ECHO.js 纯javascript轻量级延迟加载的实例代码 演示 <!DOCTYPE html> <html lang="zh-CN"> <head> <meta charset="utf-8"> <title>简单的JavaScript图像延迟加载库Echo.js</title> <style> .demo img { width: 736px; height: 490px;

  • Javascript发送AJAX请求实例代码

    一个对AJAX的封装 //url就是请求的地址 //successFunc就是一个请求返回成功之后的一个function,有一个参数,参数就是服务器返回的报文体 function ajax(url,successFunc) { var xhr = window.XMLHttpRequest ? new XMLHttpRequest() : new ActiveXObject('Microsoft.XMLHTTP'); xhr.open("POST",url,true); xhr.onr

  • JavaScript tab选项卡插件实例代码

    今天,先从最简单的开始,将已有的一个Tab选项卡切换功能改写成javascript插件形式. 原生函数写法 将一个javascript方法改写为js插件最简单的方式就是将这个方法挂载到window全局对象下面 我们先来看看最原始的使用函数写法的代码: tab.html <!DOCTYPE html> <html> <head lang="en"> <meta charset="UTF-8"> <meta http

  • 使用JavaScript实现ajax的实例代码

    AJAX = Asynchronous JavaScript and XML. AJAX 是一种创建快速动态网页的技术. AJAX 通过在后台与服务器交换少量数据的方式,允许网页进行异步更新.这意味着有可能在不重载整个页面的情况下,对网页的一部分进行更新. 实现ajax之前必须要创建一个 XMLHttpRequest 对象.如果不支持创建该对象的浏览器,则需要创建 ActiveXObject.具体方法如下: var xmlHttp; function createxmlHttpRequest()

  • 使用JavaScript实现alert的实例代码

    废话不多说了,直接给大家贴代码了,具体代码如下所示: <script> window.alert = alert; function alert(data) { var MainDiv = document.createElement("div"), p = document.createElement("p"), AllPage = document.createElement("div"), btn = document.crea

随机推荐