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

例子：有序数组中最左边的元素

题目

给定一个有序数组，返回指定元素在数组的最左边的位置

输入：A = [1, 2, 2, 2, 2, 3, 3], target = 2

输出：1

解释：第一个出现的 2 位于下标 1，是从左往右看时，第一个出现 2 的位置。

【分析】我曾经在很多公司的电面中遇到过这个题目。其实它并不难，本质上，是一个模板题，是我们解决后续问题的基础，你需要非常牢固地理解并且记忆它的代码。否则你的二分搜索就是“沙上建塔”。

这道题目可能会存在一些变形，比如：“找到有序数组中第一个出现的 2”，或者“找到数组中最后一个出现的 2”。

一个不正确的回答是：“先利用二分找到一个 2，然后再向左右两边搜索”。但是这么一来，时间复杂度就变成 O(N)。

那么有没有办法降低复杂度呢？这里我们一起来看一下在二分搜索的基础上，如何找到最左边的元素。我们还是先模拟一把。

分析

1. 模拟

我们先通过在纸笔或者脑海中使用二分法模拟一个例子。

2. 规律

可以得出目的已经变为：找到一个最终切分点 L，需要满足 [0, L) 区间里面的元素都必须小于 target，而 [L, ~) 右边的元素都 >= target。左边界操作原则如下：

查找的区间一直是一个左开右闭区间 [L, R)；
每次总是把 >= target 的区间扔掉，大于等于的不要了，然后设置 R = M；
当最后的区间元素都小于 target 的时候，移动 L，小于的也不要了，然后设置 L = M + 1。

可以总结为“这也不要，那也不要”。

那么当程序最终执行结束的时候，L 必然处于以下情况之一。

如果有序数组中存在 target，那么必然找到最左边的 target 的位置。

如果有序数组中不存在 target，那么：

当数组中的元素都比 target 小时，L 指向数组的长度，此时访问 A[L] 非法；
否则，A[L] 必然 > target。

可以总结为“要么越界，要么大于等于 target”。

3. 匹配

如果仔细一点，可以发现，这里我们在二分的时候，与传统的二分搜索相比，只是去掉了如下这个条件，最终就可以让 L 指到正确的位置。

if (A[m] == target) {
  return true;
}
复制代码

4. 边界

实际上还有几种边界情况需要讨论：

空数组，或长度为 0 的数组；
数组中的元素都小于 target；
数组中的元素都大于 target；
数组中的元素有大有小，但是 target 不存在里面；
数组中的元素只有一个 target。

以上这些边界都很重要。

建议：真实的面试中，很多人写的二分搜索的代码，经常卡在上面这几种边界上。因此，在面试中写完代码之后，主动写上测试用例是一个加分项。

模板代码一：lowerBound

int lowerBound(long[] A, int n, long target) {
  int l = 0, r = n;
  while (l < r) {
    final int m = l + ((r - l) >> 1);
    if (A[m] < target) {
      l = m + 1;
    } else {
      r = m;
    }
  }
  return l;
}
复制代码

复杂度分析：我们总是利用二分搜索一直进行下去，直接找到目标解。因此，算法的时间复杂度为 O(lgn)，空间复杂度为 O(1)。

小结

代码虽然短，但是很容易写错这块代码。

面试考察点：

循环什么时候终止？（对应代码第 3 行）
什么情况下更新左边界？如何更新的？（对应代码第 5~6 行）
什么情况下更新右边界？如何更新的？（对应代码第 7~8 行）

所有这些问题的本质，都可以归结到一个知识点：开闭原则。

变形与延伸

如果我们有了 lowerBound 函数，就可以利用 lowerBound 函数来写新的 binarySearch 算法了。

boolean binarySearch(long[] A, int n, long target) {
  int l = lowerBound(A, n, target);
  return l < n && A[l] == target;
}
复制代码

实际上，在 C++ 的 STL 库里面的 binary_search 函数就是通过这种方式实现的。

题目

接下来我们看第二个模板 upperBound，它的要求是：写一个函数 upperBound 寻找数组中给定元素的上界。注意，上界是刚好比 target 大的那个元素的位置。比如 A = [1, 1, 100, 100]，target = 1，那么 upperBound 应该返回下标 2。

分析

upperBound 函数是找一个切分点 y，使得：

所有 [0, y) 左区间里面的元素 <= target
target < 所有 [y, ~) 右区间里面的元素

根据 upperBound 的目标，我们需要调整一下二分的策略：

当 A[M] <= target 的时候，需要把 [L, M] 区间扔掉。此时需要设置 L = M + 1；
当 A[M] > target 的时候，需要把 (M, R) 区间扔掉。此时需要设置 R = M。

模板代码二 upperBound

int upperBound(long[] A, int n, long target) {
  int l = 0, r = n;
  while (l < r) {
    final int m = l + ((r - l) >> 1);
    if (A[m] <= target) {
      l = m + 1;
    } else {
      r = m;
    }
  }
  return l;
}
复制代码