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] &lt;none&gt;
#include &lt;cstdlib&gt;
#include &lt;cstddef&gt;
#include &lt;cassert&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;iterator&gt;
#include &lt;numeric&gt;
#include &lt;random&gt;
#include &lt;algorithm&gt;
#include &lt;limits&gt;

// #define NODEBUG

/**
 * Finds one duplicate number in container where the largest number in the
 * container is smaller than the size of the container.
 */
template &lt;class It&gt;
It FindOneDuplicate(It first, It last) {
  int n = static_cast&lt;int&gt;(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 &gt;= range_start &amp;&amp; element &lt;= range_end) {
        ++count;
        if (count &gt; 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 &lt;&lt; "Usage: " &lt;&lt; argv[0] &lt;&lt; " &lt;N&gt;" &lt;&lt; std::endl;
    return EXIT_FAILURE;
  }
  int n =
      static_cast&lt;int&gt;(std::strtol(argv[1], static_cast&lt;char**&gt;(nullptr), 10));
  assert(n &gt; 0 &amp;&amp; n &lt; std::numeric_limits&lt;int&gt;::max());
  std::random_device rd;
  std::mt19937 generator(rd());
  std::uniform_int_distribution&lt;&gt; dist(1, n);
  std::size_t size{static_cast&lt;std::size_t&gt;(n + 1)};
  std::vector&lt;int&gt; 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&amp; element : elements) {
    bool isduplicate = element == *duplicate;
    if (isduplicate) {
      // bold;red
      std::cout &lt;&lt; "\033[1;31m";
    }
    std::cout &lt;&lt; element;
    if (isduplicate) {
      // reset
      std::cout &lt;&lt; "\033[0m";
    }
    if (&amp;element != &amp;elements.back()) {
      std::cout &lt;&lt; ", ";
    }
  }
  std::cout &lt;&lt; std::endl;
  return EXIT_SUCCESS;
}


Since this is my first real piece of C++ code I'd love to get some code review before I start working on any open source projects.

Note that I'm trying to follow the Google C++ style guide here.
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 &lt;typename It, typename V&gt;
It find_if_extra(It first, It last, V start, V end)
{
    V count = 0;
    for (; first != last; ++first) {
        if (*first &gt;= start &amp;&amp; *first &lt;= end) {
            ++count;
            if (count &gt; 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 &lt;class It&gt;
It FindOneDuplicate(It first, It last) {
    using value_type = 
        typename std::iterator_traits&lt;It&gt;::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.