文档章节

JaveScript用二分法与普通遍历(冒泡)

丶不将就
 丶不将就
发布于 2018/12/20 18:15
字数 580
阅读 1
收藏 0

二分法 查找

  概念:

    从有序的数列中,折半查找.

  思路:

    -->  找到数组中最中间的元素,将其作为基准

    -->  从0开始判断数组中的元素,与基准进行比较

    -->  比基准小的元素,存入左边,

        比基准打得元素,存入右边

        依次递归,得出结果

 

二分法查找函数

 1  function getNum(target, Arr){    
 2         var middle = Math.floor(Arr.length / 2) ,res;
 3         var last = Arr.length;
 4         var temp;
 5         function getRes(target,Arr){
 6             count++;
 7             if (target>Arr[middle]){
 8                 temp=middle;
 9                 middle= Math.floor(middle+Math.abs(last-middle)/2);
10                 last=temp;
11             }else if(target < Arr[middle]){
12                 temp=middle;
13                 middle = Math.floor(middle-Math.abs(last - middle) / 2)  ;  
14                 last=temp;            
15             }else{
16                 res = middle;
17                 return;
18             }
19             if(last==middle){  
20                 Arr[middle]!=target;          
21                 res = "不存在";
22                 return;
23             }
24             return getRes(target,Arr);
25         };
26         getRes(target, Arr);
27         return res;
28     }

普通遍历查找函数

1 function getNum2(target, arr) {
2         for (var i = 0; i < arr.length; i++) {
3             count2++;
4             if (target == arr[i]) {
5                 return i;
6             }
7         }
8         return "不存在";
9     }

生成随机数组

 1  (function(){
 2         var arr = [];
 3         for (var i = 0; i < 50000; i++) {
 4             var flag = true;
 5             var ele = Math.floor(Math.random() * 100000);
 6             for (var j = 0; j < arr.length; j++) {
 7                 if (arr[j] == ele) {
 8                     flag = false;
 9                     break;
10                 }
11             }
12             flag && arr.push(ele);
13         }
14         for (var i = 0; i < arr.length; i++) {
15             for (var j = 0; j < arr.length - i; j++) {
16                 var temp;
17                 if (arr[j] > arr[j + 1]) {
18                     temp = arr[j];
19                     arr[j] = arr[j + 1];
20                     arr[j + 1] = temp;
21                 }
22             }
23         }
24         window.arr=arr;
25         console.log(arr);//数组生成完毕,打印结果;
26     })()

二分法查找

var count=0;
        console.log("二分法查找------------------------");
        console.time("二分法耗时");            
        console.log("结果" +getNum(31322, arr));
        console.log("查找次数为:"+count);
        console.timeEnd("二分法耗时");
        console.log("普通查找------------------------");

普通遍历

var count2=0;
        console.time("普通遍历耗时");
        console.log("结果" +getNum2(31322, arr));
        console.log("查找次数为:"+count2);
        console.timeEnd("普通遍历耗时");

将二分法与普通遍历封装为函数

 1  function run(x){
 2             count=count2=0;
 3             console.log("二分法查找------------------------");
 4             console.time("二分法耗时");
 5             console.log("结果" +getNum(x, arr));
 6             console.log("查找次数为:"+count);
 7             console.timeEnd("二分法耗时");
 8             console.log("普通查找------------------------");
 9             function getNum2(target, arr) {
10                 for (var i = 0; i < arr.length; i++) {
11                     count2++;
12                     if (target == arr[i]) {
13                         return i;
14                     }
15                 }
16                 return "不存在";
17             }
18             var count2 = 0;
19             console.time("普通遍历耗时");
20             console.log("结果"+getNum2(x, arr));
21             console.log("查找次数为:"+count2);
22             console.timeEnd("普通遍历耗时");
23         };

直接输入即可验证结果

本文转载自:https://www.cnblogs.com/AmorR/p/8058473.html

丶不将就
粉丝 1
博文 61
码字总数 0
作品 0
杭州
程序员
私信 提问
算法与数据结构(五)二叉搜索树

二叉搜索树 (Binary Search Tree) 核心是解决问题。高效解决问题。 查找问题 Searching Problem: 查找问题是计算机中非常重要的基础问题 查找问题的基础:二分查找法 Binary Search 对于有序...

天涯明月笙
2017/09/16
0
0
【python】手把手带你掌握算法基础01_二分法和选择排序法的实现

一、大O表示法 学算法就绕不开大O表示法,大O法可以告诉我们算法的时间和空间复杂度。 我们先聊点简单的,请你从1数到10,这里的复杂度是多少呢?O(10)。那么从1数到n,归纳法告诉我们,复...

徐胥
05/22
0
0
Java 9种排序算法详解和示例汇总

冒泡排序、选择排序、直接插入排序、二分法排序、希尔排序、快速排序、堆排序、归并排序、基数排序,共9中排序算法详解和代码示例。 示例中全部采用从小到大排序,编码方式为本人理解的思路,...

磊_lei
2018/06/02
0
0
数据结构学习(一)

数据结构与算法 1. 链表与数组。 2. 队列和栈,出栈与入栈。 3. 链表的删除、插入、反向。 4. 字符串操作。 5. Hash表的hash函数,冲突解决方法有哪些。 6. 各种排序:冒泡、选择、插入、希尔...

技术小甜
2017/11/16
0
0
Unity 游戏中 排序算法和查找算法记录

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/KiTok/article/details/78470287 Hello ,I am Edwin 首先谢谢大家的支持,其次如果你碰到什么其他问题的话,欢...

KitStar
2017/11/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Linux使用源码包安装软件

前言: 最近整理一些以前的学习笔记。 过去都是存储在本地,此次传到网络留待备用。 源码包 Linux软件多数免费、开源,是开发人员编写的,具有很强可读性的一组相关代码文本。 源码包 --> 编...

迷失De挣扎
今天
2
0
IPv4如何转换为IPv6?

ipv6已经逐渐在应用,现在已经有很多的运营商支持ipv6,前天我们也发布了如何让电脑使用ipv6地址?有很多朋友在问?ipv6有什么作用,它的表示方式是什么,今天我们来一起来详细了解下ipv6相关计...

xiangyunyan
今天
3
0
小白讲网络安全系列

注入攻击防护 XSS注入 SQL注入 命令注入 文件上传 文件解压缩 CSRF防护 对称加密 非对称加密 数字证书 数字签名 完整性校验 消息验证码 单向散列Hash函数 口令单向加密算法 审计日志 认证鉴权...

一刀
今天
2
0
MYSQL 嵌套事务(SAVEPOINT) 与Spring 事务传播

摘要 savepoint 关键字可以实现嵌套事务。结合savepoint关键字,更方便理解spring的事务传播。 事务嵌套 初始化表脚本 drop table t;create table t(a int, primary key(a)); 开启事务 my...

liangxiao
今天
4
0
Chrome OS 更新新版本可让Linux访问USB连接的Android设备

谷歌再次为Chrome OS带来了重大版本更新,使版本号达到了75。本次更新的一大亮点就是允许在Chrome OS上运行的Linux能够识别通过USB方式连接的Android设备,能够让用户使用Linux进行调试等等。...

linuxCool
昨天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部