Find missing number (in C++)

Find missing number

Like the missing number problem, but given a list of N integers and these integers are in the range of [X, Y].
There are no duplicates in list. Maybe one or more than one of the integers is missing in the list.
Write an efficient code to find the first missing integer

— use binary search method:

/**
 * find the missing number (the first one) in a sorted array (min to max).
 * @tparam T integral value type,
 * @param nums the sorted numbers to find missing number.
 * @param nNums number count of @a nums.
 * @param rangeMin to find the number is this range.
 * @param rangeMax to find the number is this range.
 * @param[out] result result when success.
 * @return true when success, false when params invalid.
 *
 * @note
 * - @a nums should NOT nil, valid and sorted.
 * - @a nNums should valid.
 * - rangeMin should less than rangeMax!
 */
template<typename T>
typename CPPBASE2_ENABLE_IF<CPPBASE2_IS_INTEGRAL<T>::value, bool>::type
searchFirstMissingNumber(
  const T* const nums,
  const size_t nNums,
  const T rangeMin,
  const T rangeMax,
  T& result) {
  if ((!nums) || (rangeMin >= rangeMax)) {
    return false;
  }
  const T n = (rangeMax - rangeMin) + 1;
  if (uint64_t(n) <= nNums) {
    return false;
  }
  if (nNums < 1) {
    result = rangeMin;
    return true;
  }

  size_t leftIdx = 0;
  size_t rightIdx = nNums - 1;
  T expectMin = rangeMin;
  //T expectMax = rangeMax;
  size_t midIdx;
  T expectMid;

  // e.g.1: [0, 9], {0, 1, 2, 3, 5, 6, 7, 8, 9}
  //     2: [0, 9], {0, 1, 2, 4, 5, 6, 7, 8, 9}
  //     3: [0, 9], {0, 1, 2, 3, 4, 6, 7, 8, 9}
  //     4: [0, 9], {7, 8}
  //     5: [0, 9], {9}
  //     6: [0, 9], {0}
  //     7: [0, 9], {0, 1, 2, 3, 4, 5, 7, 8, 9}
  //     8: [-3, 5], {-3, -2, -1, 2, 3, 4, 5}
  while (leftIdx <= rightIdx) {
    if (nums[leftIdx] > expectMin) {
      result = expectMin;
      return true;
    } else {
      midIdx = (leftIdx + rightIdx) / 2;
      expectMid = rangeMin + midIdx;
      const T& midNum = nums[midIdx];
      if ((midNum == expectMid)
        && ((midIdx >= rightIdx) || ((expectMid + 1) != nums[midIdx + 1]))) {
        result = expectMid + 1;
        return true;
      } else if (midNum > expectMid) {
        // search left
        rightIdx = midIdx - 1;
        //expectMax = midNum - 1;
        continue;
      }
      // search right
      leftIdx = midIdx + 1;
      expectMin = midNum + 1;
    }
  }

  throw std::logic_error("bug!");
  return false;
}

some test code:

TEST(m, large) {
  const int N = 1024 * 1024 * 100;
  std::vector<int> a;
  a.reserve(N);
  SteadyTime t1, t2;

  const Duration maxET = Duration::milliseconds(1);
  Duration sum1, sum2;

  for (int k = 0; k < 100; ++k) {
    int missingNumber = kRg->get32() % a.capacity();
    int missingNumber2 = kRg->get32() % a.capacity();
    if (missingNumber > missingNumber2) {
      std::swap(missingNumber, missingNumber2);
    }
    int offset = kRg->get32() % a.capacity();
    if (k % 2) {
      offset *= -1;
    }
    a.clear();
    for (int i = 0; i < N; ++i) {
      if (i != missingNumber && i != missingNumber2) {
        a.push_back(offset + i);
      }
    }
    int result = -1;
    t1 = SteadyTime::now();
    EXPECT_TRUE(algorithm::searchFirstMissingNumberSlow(
      a.data(), a.size(), offset, offset + (N - 1), result));
    t2 = SteadyTime::now();
    sum1 += (t2 - t1);

    EXPECT_EQ(offset + missingNumber, result);
    EXPECT_LE((t2 - t1), Duration::milliseconds(100));

    CPPBASE2_INFO("searchFirstMissingNumberSlow"
           " size " << a.size()
      << ", elapsed time " << (t2 - t1).toNanosec() << " ns, "
      << ", result = " << (offset + missingNumber));

    result = -1;
    t1 = SteadyTime::now();
    EXPECT_TRUE(algorithm::searchFirstMissingNumber(
      a.data(), a.size(), offset, offset + (N - 1), result));
    t2 = SteadyTime::now();
    sum2 += (t2 - t1);

    EXPECT_EQ(offset + missingNumber, result);
    EXPECT_LE((t2 - t1), maxET);

    CPPBASE2_INFO("searchFirstMissingNumber"
           " size " << a.size()
      << ", elapsed time " << (t2 - t1).toNanosec() << " ns, "
      << ", result = " << (offset + missingNumber));
  }

  EXPECT_LE((sum1.toNanosec() / 100), Duration::milliseconds(20).toNanosec());
  EXPECT_GE((sum1.toNanosec() / 100), Duration::milliseconds(5).toNanosec());
  EXPECT_LE((sum2.toNanosec() / 100), Duration::microseconds(10).toNanosec());
}

mysql migrate datadir

mysql migrate datadir

mysql 迁移数据目录.

  1. config file:

my.cnf / my.ini (windows) / conf.d/mysql.cnf (ubuntu) …

  1. datadir
  • datadir=/path/to/data/dir

alternative tmpdir and slave_load_tmpdir:

  • tmpdir=/path/to/tmpdir
  • slave_load_tmpdir=/path/to/slave/load/tmpdir.
  1. copy all original data in datadir to new datadir

e.g.

cp -va /path/to/orig/data/dir/ /path/to/new/data/tmpdir
mv /path/to/new/data/tmpdir /path/to/new/data/dir

troubleshoots

  • windows, mysql 8, 修改 my.ini 配置并迁移原 data 目录后后启动服务失败 ?
    • 查看服务的用户,例如改为 administrator 并提供正确密码 !!.
    • 可以先将 ...err 错误日志文件删除,然后再启动,再查看错误日志,否则可能没有错误日志 !!

例如错误信息为:

> net start mysql80

MySQL80 服务正在启动
MySQL80 服务无法启动

服务没有报告任何错误

请键入 NET HELPMSG 3534 以获得更多的帮助

see also https://yuiwong.org/gitlab/database/database/blob/master/mysql/mysql-migrate-datadir.md