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) 当要查找的数字不是输入数组中包含,会出现以下错误:
所以进行: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