1.二分查找递归与迭代实现

二分查找原理简单，细节是魔鬼。

1.递归实现

function Bsort(arr, left, right, target){
  if(left <= right){
    let mid = Math.floor((left+right)/2)
    if(arr[mid] > target){
      return Bsort(arr, left, mid-1, target)
    }else if(arr[mid] < target){
      return Bsort(arr, mid+1, right, target)
    }else{
      return mid
    }
  }

  return -1
}

const arr= [1,3,6,7,8,9,10,11]
let res = Bsort(arr, 0, arr.length-1, 1)
res

2.迭代

function Bsort(arr, left, right, target){
  while(left <= right){
    // 细节是魔鬼，这里一定是“<=”（当最后比较的为下标6和7时）

    let mid = Math.floor((left+right)/2)
    if(arr[mid] > target){
      right = mid - 1
    }else if(arr[mid] < target){
      left = mid + 1
    }else{
      return mid
    }
  }
  return -1
}

const arr= [1,3,6,7,8,9,10,11]
let res = Bsort(arr, 0, arr.length-1, 6)
res