Table of contents

计算机中二分查找是一种很重要且非常常见的算法思想。虽然二分查找思路是很好理解的，但在实现上却并不简单，需要注意很多细节和边界处理。

在实现代码之前，有一个很重要的事情是，是需要是定义一种规则，相应的在此规则下做边界的处理，这个规则即是"开闭区间的定义"

一般将分为两种情况，一种是左闭右闭，另一种是左闭右开

下面以 leetcode 724题为例，使用二分查找来解答此题。

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ， 写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例1

输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4

方案一的实现代码：

function search(nums: number[], target: number): number {
  let left = 0
  let right = nums.length - 1
  // 左闭右闭
  while (left <= right) {
    let middle: number = left + ((right-left)>>1)
    if (target > nums[middle]) {
      left = middle +1      
    } else if(target < nums[middle]) {
      right = middle -1   
    } else {
      return middle
    }
  }
  return -1
};

方案二的实现代码：

function search2(nums: number[], target: number): number {
  let left = 0
  let right = nums.length
  while (left < right) {

    let middle: number = left + ((right-left)>>1)
    if (target > nums[middle] ) {
       left =middle + 1
    } else if (target < nums[middle]) {
      right = middle
    } else {
      return middle
    }
  }
  return -1
}