But there's an easy fix: don't pick numbers from the given sequence, instead use binary search on [0,n]. Then you're guaranteed only log n iterations.