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());
}

• TODO: support iterator input.
• see also https://yuiwong.org/gitlab/cpp/cppbase2/blob/master/cppbase2/include/cppbase2/algorithm/missingnumber.hpp.