二分查找

二分查找涉及的很多的边界条件，例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？

最重要的，就是想清楚区间的含义，在 while 寻找中每一次边界的处理都要坚持根据区间的定义来操作！

区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)

1. 左闭右闭

第一种写法，我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right]。

区间的定义这就决定了二分法的代码应该如何写，因为定义 target 在[left, right]区间，所以有如下两点：

• while (left <= right) 要使用 <= ，因为 left == right 是有意义的，所以使用 <=
• if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个 nums[middle]一定不是 target，那么接下来要查找的左区间结束下标位置就是 middle - 1

function search(nums, target) {
  let left = 0
  let right = nums.length - 1
  while (left <= right) {
    const mid = Math.floor((left + right) / 2)
    if (nums[mid] === target) {
      return mid
    }
    if (nums[mid] > target) {
      right = mid - 1
    } else {
      left = mid + 1
    }
  }
  return -1
}

2. 左闭右开

定义 target 是在一个在左闭右开的区间里，也就是[left, right)

• while (left < right)，这里使用 < ,因为 left == right 在区间[left, right)是没有意义的
• if (nums[middle] > target) right 更新为 middle，因为当前 nums[middle]不等于 target，去左区间继续寻找，而寻找区间是左闭右开区间，所以 right 更新为 middle，即：下一个查询区间不会去比较 nums[middle]

function search(nums, target) {
  let left = 0
  let right = nums.length
  while (left < right) {
    const mid = Math.floor((left + right) / 2)
    if (nums[mid] === target) {
      return mid
    }
    if (nums[mid] > target) {
      right = mid
    } else {
      left = mid + 1
    }
  }
  return -1
}

3. 题目

• 二分查找