Editing Rope (data structure) (section)

=== Index ===

[[File:Vector Rope index.svg|right|x200px|thumb|Figure 2.1: Example of index lookup on a rope.]]

: ''Definition:'' <code>Index(i)</code>: return the character at position ''i''
: ''Time complexity:'' {{tmath|O(\log N)}}

To retrieve the ''i''-th character, we begin a [[Recursion|recursive]] search from the root node:

<syntaxhighlight lang="java">
@Override
public int indexOf(char ch, int startIndex) {
    if (startIndex > weight) {
        return right.indexOf(ch, startIndex - weight);
    }
    return left.indexOf(ch, startIndex);
}
</syntaxhighlight>

For example, to find the character at {{code|1=i=10}} in Figure 2.1 shown on the right, start at the root node (A), find that 22 is greater than 10 and there is a left child, so go to the left child (B). 9 is less than 10, so subtract 9 from 10 (leaving {{code|1=i=1}}) and go to the right child (D). Then because 6 is greater than 1 and there's a left child, go to the left child (G). 2 is greater than 1 and there's a left child, so go to the left child again (J).  Finally 2 is greater than 1 but there is no left child, so the character at index 1 of the short string "na" (ie "n") is the answer. (1-based index)