js二分法

二分法

对有序数组进行二分查找

• 递归实现：代码逻辑清晰
• 非递归：性能更好
• 时间复杂度O(logn)

function binarySearch(arr,target){
    
  const length = arr.length
  if(length<=0) return -1
  let start = 0 //开始位置
  let end = length-1 //结束位置
  while(start <= end){
    
    const mid = Math.floor((start+end)/2)
    const midValue = arr[mid]
    if(target<midValue){
    
      // 目标值小于中间值，向左找
      end = mid -1
    }else if(target>midValue){
    
      // 目标值大于中间值，向右找
      start = mid +1
    }else{
    
      // 相等返回值
      return mid
    }
    return -1
  }
}