Time complexity of finding predecessor for a dictionary implemented as a sorted array I'm currently reading "The Algorithm Design Manual" by Steven Skiena. On page 73, he discusses the time complexity of implementing $ Predecessor(D, k) $ and $ Successor(D, k) $ and suggests that it takes O(1) time.

If the data structure looks something like

[(k0, x), (k1, x), ...]


where the keys k0 to kn are sorted, given k, I thought the successor(D, k) would first have to search the sorted array for k ( $ O(log n) $ ) and then get the successor ( $ O(1) $ ) since the array is sorted, and hence the overall time complexity should be $ O(log n) $ instead of $ O(1) $ as mentioned in the book. This should also apply for predecessor(D, k).

For an unsorted array, the time complexity for predecessor and successor remain as $ O(n) $ since searching the unsorted array also takes $ O(n) $.

Did I misunderstand something?
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.