Don't search positions — search the answer. For a candidate value, count how many array elements are ≤ it. If that count is bigger than the value itself, the pigeonhole says a duplicate hides at or below it.