对撞指针

对撞指针是指在有序数组中，将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历。

注意：对撞数组适用于有序数组，也就是说当你遇到题目给定有序数组时，应该第一时间想到用对撞指针解题。

示例

function sum(arr,target){
  let left = 0
  let right = arr.length

  while(left<right){
    if(right>target){
      console.log('right',right)
      right--
    }else if(left<target){
      console.log('left',left)
      left++
    }
  }
}

let arr = [1,2,3,4,5,6]
let target = 3

console.log(sum(arr,target))
/*
    right 6
    right 5
    right 4
    left 0
    left 1
    left 2
*/

二分法

二分法数组对撞指针的一种

模板(确定左右边界问题)

const search = (nums,target) => {
    let left = 0
    let right = nums.length -1
    while(left <= right){
        let middle = left + ((right - left) / 2) // 防止溢出 等同于(left + right)/2
        if(nums[middle] > target){
            right = middle - 1
        }else if(nums[middle < target]){
            left = middle + 1
        }else{
            return middle
        }
    }
    return -1
}