js实现二分查找法(即折半查找)

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

1. 查找过程

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

2. 算法要求

1.必须采用顺序存储结构。

2.必须按关键字大小有序排列

3.JS实现二分查找法

a.不用递归的方法实现二分查找

//arr:已升序的数组,key:查找的元素
function(arr,key){
    let low=0,high=arr.length-1   
    while(low<=high){
        let mid=Math.flor((low+high)/2)
        if(arr[mid]===key) {
            return mid
        }else if(arr[mid]<key){
            low=mid+1
        }else if(arr[mid]>key){
            high=mid-1
        }
    }
  return -1
}

b.用递归的方法实现二分查找

//arr:已升序的数组,key:查找的元素,low为arr中的最小值下标，high为arr中的最大值下标
function binarySearch(arr,low,high,key){
  let mid=Math.floor((low+high)/2)
  if(arr[mid]===key){
    return mid
  }else if(arr[mid]<key){
    low=mid+1
    return binarySearch(arr,low,high,key)    //递归调用
  }else if(arr[mid]>key){
    high=mid-1
    return binarySearch(arr,low,high,key)    //递归调用
  }else if(low>high) {
     return -1
  }
}