You can stop the recursion when you've found an index that is smaller than what you wanted to store.

See also: https://news.ycombinator.com/item?id=48480978#48482218