JS二分查找算法详解

二分法查找，也称折半查找，是一种在有序数组中查找特定元素的搜索算法。查找过程可以分为以下步骤：

（1）首先，从有序数组的中间的元素开始搜索，如果该元素正好是目标元素（即要查找的元素），则搜索过程结束，否则进行下一步。
（2）如果目标元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半区域查找，然后重复第一步的操作。
（3）如果某一步数组为空，则表示找不到目标元素。

参考代码:

 // 非递归算法
  function binary_search(arr, key) {
   var low = 0,
    high = arr.length - 1;
   while(low <= high){
    var mid = parseInt((high + low) / 2);
    if(key == arr[mid]){
     return mid;
    }else if(key > arr[mid]){
     low = mid + 1;
    }else if(key < arr[mid]){
     high = mid -1;
    }else{
     return -1;
    }
   }
  };
  var arr = [1,2,3,4,5,6,7,8,9,10,11,23,44,86];
  var result = binary_search(arr,10);
  alert(result); // 9 返回目标元素的索引值  

 // 递归算法
  function binary_search(arr,low, high, key) {
   if (low > high){
    return -1;
   }
   var mid = parseInt((high + low) / 2);
   if(arr[mid] == key){
    return mid;
   }else if (arr[mid] > key){
    high = mid - 1;
    return binary_search(arr, low, high, key);
   }else if (arr[mid] < key){
    low = mid + 1;
    return binary_search(arr, low, high, key);
   }
  };
  var arr = [1,2,3,4,5,6,7,8,9,10,11,23,44,86];
  var result = binary_search(arr, 0, 13, 10);
  alert(result); // 9 返回目标元素的索引值

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

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

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

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

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

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

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

  • 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

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

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

  • JS二分查找算法详解

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

  • Java顺序查找算法详解

    Java顺序查找算法详解

    目录 一.查找的基本概念 1.查找表 2.关键字 3.查找 4.动态查找表与静态查找表 5.平均查找长度 二.顺序查找法 1.概念 2.实践 一.查找的基本概念 在讲顺序查找法之前先来认识一些关于查找的基本概念. 1.查找表 由同一类型的数据元素(或记录)所构成的集合 数据元素之间存在完全松散的关系 非常灵活的数据结构 2.关键字 关键字是数据元素(或记录)中某个数据项的值,可以用它标识一个数据元素(或记录) 若关键字可以唯一地标识一个记录,则称之为主关键字 反之,若用以识别若干记录的关键字称之

  • Java数据结构之图的路径查找算法详解

    Java数据结构之图的路径查找算法详解

    目录 前言 算法详解 实现 API设计 代码实现 前言 在实际生活中,地图是我们经常使用的一种工具,通常我们会用它进行导航,输入一个出发城市,输入一个目的地 城市,就可以把路线规划好,而在规划好的这个路线上,会路过很多中间的城市.这类问题翻译成专业问题就是: 从s顶点到v顶点是否存在一条路径?如果存在,请找出这条路径. 例如在上图上查找顶点0到顶点4的路径用红色标识出来,那么我们可以把该路径表示为 0-2-3-4. 如果对图的前置知识不了解,请查看系列文章: [数据结构与算法]图的基础概念和数据

  • python查找与排序算法详解(示图+代码)

    python查找与排序算法详解(示图+代码)

    目录 查找 二分查找 线性查找 排序 插入排序 快速排序 选择排序 冒泡排序 归并排序 堆排序 计数排序 希尔排序 拓扑排序 总结 查找 二分查找 二分搜索是一种在有序数组中查找某一特定元素的搜索算法.搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束:如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较.如果在某一步骤数组为空,则代表找不到.这种搜索算法每一次比较都使搜索范围缩小一半. # 返回 x 在 ar

  • Js面试算法详解

    素数 Q:你将如何验证一个素数? A:一个素数只能被它自己和1整除.所以,我将运行一个while循环并加1.(看代码示例,如果你无法理解,那这不是你的菜.先回去学习javaScript基础知识然后再回来吧.) 方法1 function isPrime(n){ var divisor = 2; while (n > divisor){ if(n % divisor == 0){ return false; } else divisor++; } return true; } isPrime(137

  • Java实现权重随机算法详解

    目录 应用场景 本文目标 算法详解 权重比例 Java 实现 参考 应用场景 客户端负载均衡,例如 Nacos 提供的客户端负载均衡就是使用了该算法 游戏抽奖(普通道具的权重很高,稀有道具的权重很低) 本文目标 Java 实现权重随机算法 算法详解 比如我们现在有三台 Server,权重分别为1,3,2.现在想对三台 Server 做负载均衡 Server1 Server2 Server3 weight weight weight 1 3 2 权重比例 我们算出每台 Server 的权重比例,权

  • Java二分查找算法与数组处理的应用实例

    Java二分查找算法与数组处理的应用实例

    目录 1.特殊数组的特征值 题目描述 思路详解 代码与结果 2.在D天内送达包裹的能力 题目描述 思路详解 代码与结果 3.咒语和药水的成功对数 题目描述 思路详解 代码与结果 总结 1.特殊数组的特征值 题目描述 思路详解 看到本题,首先思考需要排序,然后查找,这里为了效率采用二分查找. 假设定义x=(left+riht)/ 2,每次查找到nums中第一个大于等于X的元素下标,判断大于等于X的个数与X的关系,进行分情况修改左右边界. 代码与结果 class Solution { public

  • js正则表达式常用函数详解（续）

    正则表达式对象的方法 1.test,返回一个 Boolean 值,它指出在被查找的字符串中是否存在模式.如果存在则返回 true,否则就返回 false. 2.exec,用正则表达式模式在字符串中运行查找,并返回包含该查找结果的一个数组. 3.compile,把正则表达式编译为内部格式,从而执行得更快. 正则表达式对象的属性 1.source,返回正则表达式模式的文本的复本.只读. 2.lastIndex,返回字符位置,它是被查找字符串中下一次成功匹配的开始位置. 3.input ($_),返回

  • Java实现最小生成树算法详解

    Java实现最小生成树算法详解

    目录 定义 带权图的实现 Kruskal 算法 二叉堆 并查集 实现算法 Prim 算法 定义 在一幅无向图G=(V,E) 中,(u,v) 为连接顶点u和顶点v的边,w(u,v)为边的权重,若存在边的子集T⊆E且(V,T) 为树,使得 最小,这称 T 为图 G 的最小生成树. 说的通俗点,最小生成树就是带权无向图中权值和最小的树.下图中黑色边所标识的就是一棵最小生成树(图片来自<算法第四版>),对于权值各不相同的连通图来说最小生成树只会有一棵: 带权图的实现 在 <如何在 Java 中实

随机推荐