星空网 > 软件开发 > Java

js实现二分法查找

1. 二分法查找

  前提: 数据是排好序的。

  题设:给出一个有序arr,从中找出key,arr的区间是array[ low , higt].

  步骤:

  (1)mid=(low+high)/2

  (2)array[mid]与key 比较,若相等,返回mid。

  (3)if array[mid]>key,则在arryay[low,mid-1]查找

      if array[mid]<key,则在array[mid+1,higt]查找

  (4)重复(1)(2)(3)

2. 题目:用js实现二分法查找。要求:从浏览器中输入一个无序的数组以及一个需要查找的数字,输出要查找数字在排序后的数字中的位置。

    以下程序大体实现了该功能,有些还没有完善。

    需要注意的有以下几点:

    (1)在浏览器输入1,2,0,3,10 后,实际上存储的是一个字符串“1,2,0,3,10”,所以需要使用split()将其转换为字符串数组:[“1”,“2”,“0”,“3”,“10”]

         (2)使用map(function(data){return +data;})对每一个元素进行类型转换,将字符串数组转换为整型数组。

      (3)不能使用sort()直接对数组进行排序,要结合campare函数

    (4)parseInt()将数组的字符串转换为整型。

    (5)Math.floor()向下取整。

    (6) 当要查找的数字不是输入数组中包含,会出现以下错误:

  js实现二分法查找

  所以进行:if(data==key)判断。

 

    

 1 var arr = prompt("请输入一个数组(以“,”隔开):").split(",").map(function(data){ 2   return +data;}).sort(compare); 3 console.log("输入的数组,排序后是:"+arr); 4  5 var key=parseInt(prompt("请输入一个要查找的数字:")); 6 console.log("要查找的数字是:"+key); 7  8 var low=0,high=arr.length-1,mid; 9 10 arr.map(function(data){11   if(data==key){12     console.log("您要查找的数字排在第 "+fun(arr,key,low,high)+" 位");13   }14 })15 16 function compare(value1,value2){17   if(value1<value2){18     return -1;19   }else if(value1>value2){20     return 1;21   }else{22     return 0;23    }24 }25 26 function fun(arr,key,low,high){27   mid=Math.floor((low+high)/2);28   if(arr[mid]==key){29     return mid;30   }else if(arr[mid]<key){31     low=mid+1;32     return fun(arr,key,low,high);33   }else{34     high=mid-1;35     return fun(arr,key,low,high);36   }37 }

 

原标题:js实现二分法查找

关键词:JS

JS
*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。

干货收藏:各国海关特殊规定大汇总!:https://www.goluckyvip.com/news/570.html
远创国际物流:https://www.goluckyvip.com/news/5700.html
中国物流集团昨日成立!:https://www.goluckyvip.com/news/5701.html
重磅!国家出手搅场跨境物流!物流费用终于要降了:https://www.goluckyvip.com/news/5702.html
TikTok观看量达2800万!这款厨具在亚马逊频频售罄!:https://www.goluckyvip.com/news/5703.html
阿里人事调整,大淘宝总裁蒋凡分管Lazada:https://www.goluckyvip.com/news/5704.html
长治婚庆女司仪和主持人:https://www.vstour.cn/a/366176.html
北京丰台区水上乐园哪家好玩?:https://www.vstour.cn/a/366177.html
相关文章
我的浏览记录
最新相关资讯
海外公司注册 | 跨境电商服务平台 | 深圳旅行社 | 东南亚物流