你的位置:首页 > Java教程

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

  

  所以进行: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 }