34. 在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

class Solution {
  int binarySearch(vector<int> &Nums, int Target, bool LowerBound) {
    int Left = 0;
    int Right = Nums.size() - 1;
    int Ans = Nums.size();
    while (Left <= Right) {
      int Mid = (Left + Right) / 2;
      if (Nums[Mid] > Target || LowerBound && Nums[Mid] == Target) {
        Right = Mid - 1;
        Ans = Mid;
      } else {
        Left = Mid + 1;
      }
    }
    return Ans;
  }

public:
  vector<int> searchRange(vector<int>& nums, int target) {
    int Lower = binarySearch(nums, target, true);
    int Upper = binarySearch(nums, target, false) - 1;
    if (Lower <= Upper && nums[Upper] == target && nums[Lower] == target)
      return {Lower, Upper};
    else
      return {-1, -1};
  }
};

这题直接让我理解了下界和上界是什么意思，也理解了 <algorithm> 里为什么要设计两个 lower_bound() 和 upper_bound()。

首先是朴素二分总是选择向下取整，并且对于大于、等于和小于的情况是分三类来讨论的；但是这题的要求并不是这样。评论区里指示我们可以这样理解，这种思考方式我觉得比较容易理解，就是为什么我们只分两类？原因就是我们要找的是界，而不是点。朴素三分的方法找的是点。

而且你可以发现，分两类也就意味着 if 语句只有两个分支，这是什么意思？其实就是「在界内或者不在界内」的区别。Ans 的默认值是数组上界，也是因为我们把它的赋值语句放在了 if 分支里。如果放在 else 分支里，那就要设定成数组下界了。

lower_bound() 和 upper_bound() 可以根据这个题解来进行了解。

二刷

class Solution {
  // This is exactly how std::lower_/upper_bound are implemented.
  int Bound(vector<int> &Nums, int Target, bool Upper) {
    int Size = Nums.size();
    int L = 0, R = Size;
    while (L != R) {
      int M = (L + R) / 2;
      bool Cond = (!Upper && Nums[M] < Target) ||
                  (Upper && Nums[M] <= Target);
      if (Cond)
        L = M + 1;
      else
        R = M;
    }
    return L;
  }

public:
  vector<int> searchRange(vector<int>& nums, int target) {
    int LowerBound = Bound(nums, target, false);
    int UpperBound = Bound(nums, target, true);
    // This line checks for existence. It also validates UpperBound - 1.
    if (LowerBound == UpperBound)
      return {-1, -1};
    // Note that further comparison like nums[UpperBound - 1] == target is not
    // necessary, since when we have LowerBound < UpperBound, we automatically
    // have UpperBound > 1.
    return {LowerBound, UpperBound - 1};
  }
};

这道题的 Bound() 的实现和 libstdc++ 当中的实现完全等价。

要注意的是，这道题其实不止求上下界这么简单——在求完上下界之后，还要判断求出的上下界是否重叠，也即是否有 LowerBound == UpperBound。如果是，那么就说明 target 在 nums 中根本不存在，所以直接返回 {-1, -1}；

如果不是这样，那么顺便也就确保了 UpperBound - 1 是大于 0 的，我们也不用再去判断具体元素的值究竟是否等于 target，所以直接返回下界和上界减一即可。

三刷

class Solution {
  int LowerBound(vector<int> &V, int Target) {
    int L = 0, R = V.size();
    while (L != R) {
      int M = L + (R - L) / 2;
      if (V[M] < Target)
        L = M + 1;
      else
        R = M;
    }
    return L;
  }
  int UpperBound(vector<int> &V, int Target) {
    int L = 0, R = V.size();
    while (L != R) {
      int M = L + (R - L) / 2;
      if (V[M] <= Target)
        L = M + 1;
      else
        R = M;
    }
    return L;
  }
public:
  vector<int> searchRange(vector<int>& nums, int target) {
    if (nums.empty())
      return {-1, -1};
    int Lower = LowerBound(nums, target);
    int Upper = UpperBound(nums, target);
    // Check both boundary and exactness. Just the lower bound is enough.
    if (Lower < nums.size() && nums[Lower] == target)
      return {Lower, Upper - 1};
    else
      return {-1, -1};
  }
};

哎我操，对啊，二刷那个LowerBound == UpperBound很神啊，都不需要check什么越界之类的了，牛逼。