二分查找和 Lucas 定理

因为这段时间都在打比赛中度过，有几个小的收获点这边可以留个纪念。

1. 二分查找的几个用法。

一般而言，二分查找都是用在不同数字的数量集中。这样的好处是如何快速的定位。但是，如果是排序的包含相同数字的数组，要求获得某一个数出现的次数时，就得用另一种二分查找的变种了。

假设是 [1, 1, 2, 3, 3] 这样的一个数组，要求获得 1 和 3 的个数时。普通的二分查找只能定位到其中的一个位置。之前我的做法是，向前向后搜索。但是，在极端情况下，比如一整个数组都是 1，此时，算法的复杂度退化为 O(N)，然后就 TLE 了。

所以这边也正好是看到【剑指 offer 】里面有这么一题，就写一下。

int getFirstIdx(vector<int> &nums, int target) {
  if (nums.size() == 0) {
    return -1;
  }
  int left = 0, right = nums.size() - 1;
  do {
    int mid = left + (right - left) / 2;
    if (mid == target) {
      if (mid == 0 || (mid > 0 && nums[mid - 1] != target)) {
        return mid;
      } else {
        left = mid - 1;
      }
    } else if (mid > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  } while (left <= right);
  return -1;
}
int getLastIdx(vector<int> &nums, int target) {
  if (nums.size() == 0) {
    return -1;
  }
  int left = 0, right = nums.size() - 1;
  do {
    int mid = left + (right - left) / 2;
    if (mid == target) {
      if (mid == (int)nums.size() - 1 ||
          (mid < (int)nums.size() - 1 && nums[mid + 1] != target)) {
        return mid;
      } else {
        right = mid + 1;
      }
    } else if (mid > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  } while (left <= right);
  return -1;
} 

这样就可以获得到，在数组中的开始和结束位置了。这样，即使是最坏情况，也是 O(logN) 的复杂度了。

2. lucas 定理

也是我在 hiho 挑战赛上得一个收获吧。当时是 80/100 的数据过了，但是最后是 WA，很明显是一个溢出问题。因为中间过程中要求组合数 C(n, m)，其中，n 和 m 都可能很大。

当时比较傻的做法就是，在计算阶乘的过程中，不停的去查有没有可能进行提前的约分。但是，最后是 TLE 。然后查了一下，发现了这个算法。

其中这个数学证明很有意思。先说结论 C(n, m) % p = C(n / p, m / p) * C(n % p, m % p) % p。

证明的话，参考维基百科。

具体的代码实现如下：

uint64_t powMod(uint64_t a, uint64_t b, uint64_t p) {
  uint64_t res = 1;
  while (b != 0) {
    if (b & 1) res = (res * a) % p;
    a = (a * a) % p;
    b >>= 1;
  }
  return res;
}
uint64_t comb(uint64_t a, uint64_t b, uint64_t p) {
  if (a < b) return 0;
  if (a == b) return 1;
  if (b > a - b) b = a - b;
  uint64_t ans = 1, ca = 1, cb = 1;
  for (uint64_t i = 0; i < b; ++i) {
    ca = (ca * (a - i)) % p;
    cb = (cb * (b - i)) % p;
  }
  ans = (ca * powMod(cb, p - 2, p)) % p;
  return ans;
}
uint64_t C(int n, int m, int MOD) {
  uint64_t ans = 1;
  while (n && m && ans) {
    ans = (ans * comb(n % MOD, m % MOD, MOD)) % MOD;
    n /= MOD;
    m /= MOD;
  }
  return ans;
} 

这几个也算是填充了我的模板库了。