这是我参与更文挑战的第 16 天，活动详情查看：更文挑战

二分搜索

二分搜索在工程中有很多的应用，比如：操作系统、MySQL 、Hadoop、Spark，查找数据的时候都会用到二分搜索。

二分搜索基础

二分搜索的目的是在一个有序的数组 A 里面，找到一个给定的数。比如我们想要在下面的数组里面查找 target=3。（小写字母 l 与 1 不太容易区分，文中都用大写 L 来表示。但是在图片和代码中，仍然用小写。）

下面我们来分析一下这段代码

boolean binarySearch(long[] A, long target) {
  if (A == null || A.length == 0) {
    return false;
  }
  // 首先设定初始区间，这里我们采用开闭原则[l, r)
  int l = 0, r = A.length;
  // 循环结束的判断条件是整个区间为空区间，那么运行结束。
  // 我们使用的是开闭原则来表示一个区间，所以当l < r的时候
  // 我们要查找的区间还不是一个空区间。
  while (l < r) {
    final int m = l + ((r - l) >> 1);
    if (A[m] == target) {
      return true;
    }
    if (A[m] < target) {
      // 当中点比目标值小时，需要把左边的部分扔掉。即[l, m]
      // 这个区间扔掉，由于我们采用的是开闭原则，所以新的区间需要是
      // [m + 1, r), 因引需要将l = m + 1
      l = m + 1;
    } else {
      // 当中点比目标值大时，需要把右边的部分扔掉，即[m, r)这个区间扔掉。
      // 那么新区间变成[l, m)。由于我们使用的是开闭原则，
      // 只需要设置r = m即可。
      r = m;
    }
  }
  return false;
}
复制代码

复杂度分析：在实行二分查找时，由于每次我们都会扔掉一半的数据，所以总共只需要 O(lgn)的时间复杂度，空间复杂度是 O(1)。

小结

虽然二分搜索是一个非常基础的题目，但作为面试官，我看到很多候选人一不小心就栽在它上面。因此，这里我需要重点强调一下二分搜索里面的几个关键考点。

开闭原则，开闭原则是一段区间的表示法。你一定要注意，写二分搜索的时候，每一个区间的表示都是严格按照开闭原则进行的。这是面试中一个非常重要的考点（敲黑板，我待过的几家公司都喜欢考察）。
区间的变化，要深度理解区间的三种情况：
1. 扔掉左区间为什么是 L = M + 1，扔掉右区间为什么是 R = M；
2. 为什么一个 L 要加 1，一个 R 不加 1；
3. 为什么循环的条件需要是 L < R。
代码流畅度，这已经是一个非常非常基础的算法了，如果你在写代码的时候还会出现卡壳，那么我建议你思考以下两个问题：
1. 是否真的深度理解开闭原则在二分搜索里面的体现？
2. 是否真的记住这个代码模板了？