Find one duplicate in container with N+1 integers between 1 and N

Time complexity is supposed to be \$O(n \cdot \log(n))\$ and space complexity is supposed to be \$O(1)\$. Neither the elements of the container nor the container should be modified.

```
// Copyright [2015]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

// #define NODEBUG

/**
* Finds one duplicate number in container where the largest number in the
* container is smaller than the size of the container.
*/
template
It FindOneDuplicate(It first, It last) {
int n = static_cast(std::distance(first, last) - 1);
int range_start = 1;
int range_end = n / 2;
while (true) {
next_range:
int range_size = range_end - range_start + 1;
int count = 0;
for (auto current{first}; current != last; ++current) {
int element = *current;
if (element >= range_start && element range_size) {
n = range_end;
range_end = (n + range_start) / 2;
if (range_size == 1) {
return current;
}
// break and continue
goto next_range;
}
}
}
// This should never happen
assert(range_end != n);

range_start = range_end + 1;
range_end = n;
}
}

// This is just a test run
int main(int argc, char* argv[]) {
if (argc != 2) {
std::cerr " (std::strtol(argv[1], static_cast(nullptr), 10));
assert(n > 0 && n ::max());
std::random_device rd;
std::mt19937 generator(rd());
std::uniform_int_distribution<> dist(1, n);
std::size_t size{static_cast(n + 1)};
std::vector elements(size);
// Fill and increment except last
std::iota(elements.begin(), elements.end() - 1, 1);
// Fill last with random value [1..N]
elements.back() = dist(generator);
// Shuffle elements
std::shuffle(elements.begin(), elements.end(), generator);
auto duplicate = FindOneDuplicate(elements.begin(), elements.end());
for (const auto& element : elements) {
bool isduplicate = element == *duplicate;
if (isduplicate) {

Never use goto

There are times where you have a compelling reason to use goto. This really isn't one of them. Either make your function recursive, since it is in all but name. Or rewrite it to be iterative. Both of those would be preferred solutions. The reason I say this is because your logic is sort of logic a binary search, except the two different changes in range occur in different places and use different mechanisms. This makes it difficult to understand and, I imagine, debug.

A Better Algorithm

Add a helper function that will count the number of elements in your given range, breaking out early if you hit the amount you're going for:

template 
It find_if_extra(It first, It last, V start, V end)
{
    V count = 0;
    for (; first != last; ++first) {
        if (*first >= start && *first  end - start + 1) {
                return first;
            }
        }
    }

    return last;
}

This is basically the same thing you were doing in your loop, except substituting the return/goto pair for two returns. Now, we can just rewrite your original function to use this helper and the goto goes away:

template 
It FindOneDuplicate(It first, It last) {
    using value_type = 
        typename std::iterator_traits::value_type;

    value_type N = std::distance(first, last) - 1;
    value_type start = 1;
    value_type end = N/2;

    for (;;) {
        auto it = find_if_extra(first, last, start, end);

        if (it != last) {
            // recurse lower unless we're done
            if (start == end) {
                return it;
            }

            N = end;
            end = (N + start) / 2;
        }
        else {
            // recurse higher
            start = end + 1;
            end = N;
        }
    }
}

Assumptions on types

There's no reason to cast n to be an int. size_t is fine:

size_t n = std::distance(first, last) - 1;

Similarly, I would initialize element with auto. You take arbitrary iterators, what if we had a huge container of size_t? You'd overflow.

Also, avoid this construction:

auto current{first};

in favor of

auto current = first;

The former may change meaning in the future, and there's no reason to prefer it anyway.

Testing

Your test just outputs something to the screen. Ideally, you would write test that actually verify the behavior of your program.

StackExchange Code Review Q#111547, answer score: 5