JS算法之二分查找法获取指定数值

  • 更新时间:5年零207天前
  • 浏览量:2105
  • 发布人:思过崖

二分查找法的使用场景

  • 数据量比较大
  • 数据按照从小到大的顺序进行排列
问题:给定一个数组[1,2,4,8,16,32,64,128,256,512,1024,2048,4096],使用JS二分查找算法获取2048在数组中的下标
  1. var arr=[1,2,4,8,16,32,64,128,256,512,1024,2048,4096];
  2. function findIndex (arr,value) {
  3. var minIndex=0;
  4. var maxIndex=arr.length-1;
  5. var midIndex=parseInt(arr.length/2)
  6. //数值判断,避免无效查询
  7. if(arr[minIndex]>value || arr[maxIndex]<value){
  8. return false;
  9. }
  10. while(minIndex<=maxIndex){
  11. var midIndex=parseInt((minIndex+maxIndex)/2);
  12. if(arr[midIndex]==value){
  13. return midIndex;
  14. }
  15. //如果没有+1和-1,在查找不存在的数值时会造成死循环
  16. if(arr[midIndex]>value){
  17. maxIndex=midIndex-1;
  18. }else{
  19. minIndex=midIndex+1;
  20. }
  21. }
  22. return false;
  23. }
  24. alert(findIndex(arr,250));