Unsuccessful searches can be represented by augmenting the tree with "external nodes", which forms an "extended binary tree". If an internal node, or a node present in the tree, has fewer than two child nodes, then additional child nodes, called external nodes, are added so that each internal node has two children. By doing so, an unsuccessful search can be represented as a path to an external node, whose parent is the single element that remains during the last iteration. An "external path" is a path from the root to an external node. The "external path length" is the sum of the lengths of all unique external paths. If there are formula_2 elements, which is a positive integer, and the external path length is formula_129, then the average number of iterations for an unsuccessful search formula_130, with the one iteration added to count the initial iteration. The external path length is divided by formula_131 instead of formula_2 because there are formula_131 external paths, representing the intervals between and outside the elements of the array.