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