二分法 左闭右闭 左开右闭 的区别

const res = search([1, 2, 3, 4, 534, 34, 2], 34)
console.log(res)

function search(nums: number[], target: number): number | void {
  // [left,right] : 左闭右闭的情况
  let left = 0
  let right = nums.length - 1 // 因为是右闭,所以right = nums.length-1
  while (left <= right) { // 这里是<=,比如说[1,1]
    let middle = (left + right) / 2
    // 首先通过前面的 nums[middle]>target , 我们已经判断这个middle不是了,所以就是right=middle-1 ,
    // 试想,如果right=middle,加上我们是左闭右闭,所以在接下来的循环中我们其实多把middle计算了
    if (nums[middle] > target) right = middle - 1
    else if (nums[middle] < target) left = middle + 1
    else return middle
  }
  return
}

console.log('----------------------------------')
const res2 = search([1, 2, 3, 4, 534, 34, 2], 34)
console.log(res2)
function search2(nums: number[], target: number): number | void {
  // [left,right) : 左闭右开的情况
  let left = 0
  let right = nums.length // 因为是右开,所以right = nums.length
  while (left < right) { //这里就不能填写 <=,很明显[1,1),就是不合理的逻辑
    let middle = (left + right) / 2
    // 因为是左必右开,所以我们的左边实际上是不会算在里面的,所以right=middle,这个middle是不会算在里面的.
    // 而如果right=middle-1,然后这个middle-1,则会被漏掉,因此,right=middle,这和上面的左闭右闭情况有区分
    if (nums[middle] > target) right = middle
    else if (nums[middle] < target) left = middle + 1
    else return middle
  }
  return
}

原文地址：http://www.cnblogs.com/zhuoss/p/16823454.html