Suppose we are given a sorted array A$[1...$ n$],$ and we wish to determine where in A the element

x belongs$$that is$,$ the index i such that A$[$i $1]<$ x $<=$ A$[$i$].($Binary Search solves this problem.$)$ Here$$s a

sketch of an algorithm rootSearch to solve this problem: