二分查找那些事

二分查找是我们比较常用的搜索算法，针对有序数组，可以将时间复杂度控制在O(logn)，它的原理也相当简单，以至于我们在学习的时候就觉得这样的查找算法我们可以信手拈来，但是事实确实如此吗？
朴素二分查找或许就是我们觉得非常简单的二分查找算法了，我们可以先来看看它的代码。

朴素二分查找

int myBinarySearch(vector<int> A,int val){
  int left = 0;
  int right = A.size()-1;
  int mid;
  while(left<=right){
    mid = (left+right)>>1;
    if(A[mid]<val){
      left = mid+1;
    }else if(A[mid]>val){
      right = mid-1;
    }else{
      return mid;
    }
  }
  return -1;
}

以上代码相信大家都熟悉得不能再熟悉了，简直是教科书般的二分查找。这个代码有什么优点呢？简单！大家一眼都能看懂，也明白原理。那么有什么缺点呢？大家是不是总会感觉这个代码弱了一些。只能找到某个确切的值。试想一种情况，如果存在多个相同的值，且需要找到最左边的那个值的下标（最右边的情况类似），这个时候朴素二分查找怕是无能为力了，它能找到，但是找到的并不是最左边的那个。当然，我们可以进行改进一下。

---

朴素二分查找改进版，存在相同值找最左边的下标

int myBinarySearch(vector<int> A,int val){
  int left = 0;
  int right = A.size()-1;
  int mid;
  while(left<=right){
    mid = (left+right)>>1;
    if(A[mid]<val){
      left = mid+1;
    }else if(A[mid]>val){
      right = mid-1;
    }else{
      while(A[mid]==A[mid-1]) mid--;
      return mid;
    }
  }
  return -1;
}

可以看到，上面的代码对朴素二分查找进行了一些改进，在找到val值之后，一直往左边找与它相同的值，直至最左边的val，返回其下标。当然，这段代码也是很简单，非常简单暴力，一目了然。
再考虑一种情况，如果要找的val值它不存在，我也要求找到第一个大于它的值的下标，如果存在并且在有值相同的情况下，要找到最左边的val的下标。简而言之，就是需要找到第一个大于等于val的值的下标。细心的同学可能马上就知道了，这不就是c++ stl库中容器的lower_bound方法吗？对，就是要实现这个方法。（upper_bound方法类似，有兴趣的同学可以根据下面代码自己尝试写）

---

二分查找再升级，找第一个大于等于val的值的下标

int getPos(vector<int> A, int n, int val) {
      A.insert(A.begin(),INT_MIN);
        A.insert(A.end(),INT_MAX);
        int s = 0;
        int e = A.size()-1;
        while(s<e-1){
            int mid = (s+e)>>1;
            if(A[mid] < val){
                s = mid;
            }else{
                e = mid;
            }
        }
        return e;
    }

在上面的代码中，个人认为非常非常重要的一点是在数组的开头和结尾分别加了哨兵，这样就可以在一定程度上较好地处理了val比数组的最小数字都小和最大数字都大的情况。当然，这里的哨兵完全可以由先进行数组首元素和尾元素大小进行判断来代替，只要确保能处理以上极端情况即可。加哨兵的好处在于整体看起来更统一化，而预先判断的好处显而易见，开销小；大家应该都发现了，一个数组加哨兵的复杂度在O(N)，这显然远大于二分查找的O(logN)。在最左化处理上，这边在A[mid]>=val的时候令e=mid，从而实现e向左移动，同时也保证了A[e]必然是大于等于val的。同样的，令A[mid]<val的时候，令s=mid，这也是保证了A[s]是始终小于val的。
所以我们现在要担心的是循环跳出条件（这个很重要！因为有可能达不到循环跳出条件，一不小心就出现死循环。）我们看到循环条件是s<e-1，那么在s=e-1的时候就会跳出循环。
可以用反证法来证明，假设最终s和e的差值始终保持在大于1的状态，即大于等于2，那么(s+e)/2>=(2s+2)/2=s+1；同理，对于e来说，(s+e)/2<=(2e-2)/2=e-1 。即mid小于e并且大于s。此时在经过一轮循环后，s或e会被赋值为mid，这时s和e的差值会缩小，与s和e的差值始终保持在大于1的状态矛盾。

另外，值得一说的是，此处返回e是在加了哨兵情况下的下标。

---

2018.5.26更新

因为不是专业搞c++的，今天有大佬私信我，告诉我代码中有两处值得商榷。 二分查找那些事
其中一处，是vector参数传递，我这边用了传值的方式，相对来说用传引用的方式会更快一些。另外一处就是vector的size函数返回size_t，在我的代码中隐式转换成int，在32位平台上返回无符号int，在64位上返回无符号long long。这两个点值得注意。虽然，程序不存在致命问题，但是有些时候，这些问题往往会造成较大的开销和不稳定性。

另外附上修改后的朴素二分查找代码，其他两个也是类似修改。

int myBinarySearch(vector<int> const& A,int val){
  long long left = 0;
  long long right = static_cast<long long>(A.size())-1;
  long long mid;
  while(left<=right){
    mid = (left+right)>>1;
    if(A[mid]<val){
      left = mid+1;
    }else if(A[mid]>val){
      right = mid-1;
    }else{
      return mid;
    }
  }
  return -1;
}