二分查找

1. 开区间与闭区间
   开区间——意味着是开的，也就是没有端点 ( )
   闭区间——意味着关闭的，也就是有端点 [ ]

搜索区间：左闭右开 [left, right)

2. 代码框架

用于在排好序的数组中找一个数

int left;
int right;

while(xxx) {
      int mid = left + (right - left) / 2;
      if(mid == target) {
          return mid;
      } else if(mid > target) {
          right = 
      } else {
          mid = 
      }
}

搜索边界值，如在可能的区间 [1, n] 中 ，对于[1, target) 不合格，对于[target,n]合格

int left;
int right;

while(xxx) {
      int mid = left + (right - left) / 2;
      if(mid == target) {
          return mid;
      } else {
          
      }
    return xxx;
}

3. 两大要义
   （1）能够把整个搜索区间搜完
   （2）在缩小区间的时候，要保证可能的答案会被保留。

理解，对于第一点来说，我们举一个极端的例子

while(left < right - 3)
很明显，他是无法搜索整个区间的

这样，就诞生了 while(left < right) 和 while(left <= right) 两种写法
那么到底应该是哪种呢？这取决于 最初的left和right的取值
假设我们要在一个有序数组中查找某一个值，数组长度为length

有两种left 和 right的初值

一、 left = 0; right = n - 1;
这种的话，真正的答案区间就是[left , right]
那么对于它而言，
由于我们使用了int mid = (left + mid) / 2;
我们考虑极端情况，最终的结果是right，
假设我们使用的是while(left < right) ，那么，我们是不会对right进行判断的，在判断到right - 1的时候，就退出循环了。

left = 0; right = n;
这种的话，真正的答案区间是[left, right)

4. 二分查找的另一种分类方法
   (1)在查找区间内能够找到答案
   (2)在查找区间内，可能找不到答案

left = min;
right = max;

如果我们都使用while(left < right)的话，对于第一种情况，右区间不需要扩张，我们会查找到 min ~ max - 1 ，我们无法判断right，但是由于一定能够找到答案，所以若在min ~ max - 1找不到答案，那么最终答案一定是max

left = min;
right = max + 1;

对于第二种情况，我们右区间需要扩张一个格子，即right应当为max + 1 其中，max是最大的可能值，这样，我们会判断从min ~ max的任意一个值。同时，在循环内部，应当保障右开，即，right应当是可能性 + 1。

练习这道题的 https://leetcode-cn.com/problems/find-in-mountain-array/