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 返回目标元素的索引值
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。
相关推荐
-
JavaScript使用二分查找算法在数组中查找数据的方法
本文实例讲述了JavaScript使用二分查找算法在数组中查找数据的方法.分享给大家供大家参考.具体分析如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表.首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一
-
javascript实现二分查找法实现代码
一般二分都用到int[]型上.....在js中可能会更灵活的用到a-z上,或者用到拼音...或者用到...... 不过值得深思的一个问题是,如果为了实现对拼音之类的二分查找.而经过如下流程是否值得: 1.对拼音排序,貌似代码量不小吧. 2.然后再二分查找.这又需要识别拼音的大小,貌似也不算太小吧. 找到结果的速度快了,可是别人下你的js文件速度慢多了,呵呵,到底舍弃谁. 下面的代码甚至可以10亿条,一样会很快找到,可是用遍例的模式创建那个数组...所以还是别尝试了.只是给个思路,下次我再来发个j
-
js基本算法:冒泡排序,二分查找的简单实例
知识扩充: 时间复杂度:算法的时间复杂度是一个函数,描述了算法的运行时间.时间复杂度越低,效率越高. 自我理解:一个算法,运行了几次时间复杂度就为多少,如运行了n次,则时间复杂度为O(n). 1.冒泡排序 解析:1.比较相邻的两个元素,如果前一个比后一个大,则交换位置. 2.第一轮的时候最后一个元素应该是最大的一个. 3.按照步骤一的方法进行相邻两个元素的比较,这个时候由于最后一个元素已经是最大的了,所以最后一个元素不用比较. function sort(elements){ for(var i
-
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顺序查找算法详解
目录 一.查找的基本概念 1.查找表 2.关键字 3.查找 4.动态查找表与静态查找表 5.平均查找长度 二.顺序查找法 1.概念 2.实践 一.查找的基本概念 在讲顺序查找法之前先来认识一些关于查找的基本概念. 1.查找表 由同一类型的数据元素(或记录)所构成的集合 数据元素之间存在完全松散的关系 非常灵活的数据结构 2.关键字 关键字是数据元素(或记录)中某个数据项的值,可以用它标识一个数据元素(或记录) 若关键字可以唯一地标识一个记录,则称之为主关键字 反之,若用以识别若干记录的关键字称之
-
Java数据结构之图的路径查找算法详解
目录 前言 算法详解 实现 API设计 代码实现 前言 在实际生活中,地图是我们经常使用的一种工具,通常我们会用它进行导航,输入一个出发城市,输入一个目的地 城市,就可以把路线规划好,而在规划好的这个路线上,会路过很多中间的城市.这类问题翻译成专业问题就是: 从s顶点到v顶点是否存在一条路径?如果存在,请找出这条路径. 例如在上图上查找顶点0到顶点4的路径用红色标识出来,那么我们可以把该路径表示为 0-2-3-4. 如果对图的前置知识不了解,请查看系列文章: [数据结构与算法]图的基础概念和数据
-
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二分查找算法与数组处理的应用实例
目录 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实现最小生成树算法详解
目录 定义 带权图的实现 Kruskal 算法 二叉堆 并查集 实现算法 Prim 算法 定义 在一幅无向图G=(V,E) 中,(u,v) 为连接顶点u和顶点v的边,w(u,v)为边的权重,若存在边的子集T⊆E且(V,T) 为树,使得 最小,这称 T 为图 G 的最小生成树. 说的通俗点,最小生成树就是带权无向图中权值和最小的树.下图中黑色边所标识的就是一棵最小生成树(图片来自<算法第四版>),对于权值各不相同的连通图来说最小生成树只会有一棵: 带权图的实现 在 <如何在 Java 中实
随机推荐
- vue中计算属性(computed)、methods和watched之间的区别
- Java中getResourceAsStream用法分析
- JavaWeb开发中alias拦截器的使用方法
- IOS 的弹性滚动解决方案
- javascript时间戳和日期字符串相互转换代码(超简单)
- asp.net自定义分页控件示例
- php运行时动态创建函数的方法
- Python中unittest模块做UT(单元测试)使用实例
- 一个开发人员眼中的JSP技术(下)
- C#将字母或数字加密成字母的方法
- AJAX 随记
- c#实现摄像头拍照功能示例
- Ajax获取XMLHttp对象的方法
- SQL Server存储过程生成insert语句实例
- js实现简单的星级选择器提交效果适用于评论等
- 二级连动菜单
- Http上传与Ftp上传的区别详解
- java导出数据库的全部表到excel
- 劲舞团服务器架设教程初窥探讨篇
- android ListView结合xutils3仿微信实现下拉加载更多