二分法

二分法是搜索算法中极其典型的方法，其要求输入序列有序并可随机访问。算法思想为

输入：有序数组nums，目的数值target 要求输出：如果target存在在数组中，则输出其index，否则输出-1

  1. 将原数组通过[left,right]两个索引划分范围，初值left=0,right=数组的最后一个元素
  2. 当left <= right时
    1. middle = (left + right)/2
    2. 判断nums[middle]是不是要查找的target，如果是则返回结果
    3. 判断nums[middle]> target，证明要查找的target在左边，因此right = middle - 1
    4. 判断nums[middle]< target，证明要查找的target在右边，因此left = middle + 1
  3. 没有查找到return -1。

这里要注意两个问题：

  1. 上述算法中的第2步中=的判断。
  2. 上述算法2.2-2.4中的判断条件

首先对于第一个问题，=是否应该存在，取决于对于二分查找的初始化定义，例如：

  1. 如果二分查找遍历的区间采用[left,right]的形式，考虑left==right即=成立的情况，则表示区间内只有单个操作数，这种情况还是需要处理，否则无法通过其余方式表示这种情况，所以此时=是必须的。
  2. 如果二分查找遍历的区间采用[left,right)的形式，考虑left==right即=成立的情况，事实证明，这种情况并不应该存在，我们无法用[i,i)表示任何一个区间，所以，这种情况下，=就不是必须的。

然后考察对于第二个位置，判断条件应该如何设置，对于元素唯一且等值问题，原始算法可以满足条件，但有时存在元素不唯一且等值或元素不唯一且不等值问题，例如下题：34. 在排序数组中查找元素的第一个和最后一个位置，此题目就是一个典型的元素不唯一的等值问题，对于此类问题，需要灵活考虑：

  1. 当遍历到当前值nums[i] == target时应该怎样处理
  2. 当遍历到当前值nums[i] > target时应该怎样处理
  3. 当遍历到当前值nums[i] < target时应该怎样处理

该问题的详解请查看34. 在排序数组中查找元素的第一个和最后一个位置。

其实这里还有一个很关键的问题，如果查找到了当前值，left指针会在哪儿，right指针会在哪儿呢？在不同的条件下，灵活利用两个指针的位置就可以解决更多问题。

此类问题应为边界条件特殊的问题。还有一类问题是可以用二分查找的应用问题。

二分查找边界条件特殊问题

  1. 34. 在排序数组中查找元素的第一个和最后一个位置：强烈建议阅读

二分查找常见变体

  1. 查找第一个大于等于x的值
/**
* 注意搜索区间为nums[l,r]，两边都是闭区间
*/
func search(nums []int, l,r int, x int) {
   for l <= r {
      middle := (l+r)/2
      if nums[middle] < x {
         // nums[middle] < x时，要查找的值一定出现在middle右侧
         l = middle + 1
      } else {
         // nums[middle] >= x时，要查找的值可能出现在middle左侧或者就是当前的nums[middle]值
         r = middle - 1
      }
      return left
   }
}

对于此类问题的具体解释在34. 在排序数组中查找元素的第一个和最后一个位置中