Time complexity of finding predecessor for a dictionary implemented as a sorted array
It's true that on page 73, the author defines the abstract functions $Predecessor(D, k)$ and $Successor(D, k)$, which find the predecessor and successor of a given key. 

But the chart on page 74 lists the interfaces as $Predecessor(L, x)$ and $Successor(L, x)$, which find the predecessor and successor of a given entry index. Clearly this is O(1) for a sorted random access datastructure.

This particular interface is, in general, more useful and more efficient than the key-based interface previously presented, since it more accurately represents the cost of iterating through the dictionaries elements. Most such interfaces do, in fact, take some kind of cursor ("iterator" in C++ parlance) as an argument and return another cursor as a result.