The Statement: Suppose that some unsuccessful search in a red-black binary serach tree terminates after k key compares. Then, any unsuccessful search performs at least ceiling(k/2) key compares.
The explanation of why it is correct: In the extreme case, the links alternate between red and black (starting with red) and the black height is ceiling(k/2) - 1. Any unsuccessful search traces a path from the root to a null link; there are exactly ceiling(k/2) - 1 black links (not including the null link) along such a path. If the path contains no red links, then it contains ceiling(k/2) nodes (and makes ceiling(k/2) key compares).
My opinion: unless k = 0 or 1, it is not possible that k == ceiling(k/2). I begin to think maybe the issue is how I interpret the statement.
If some unsuccessful search takes k compares, then every unsuccessful search must take at least ceil(k/2) compares.
That includes the one that takes k compares, since k is at least ceil(k/2).
Note that "at least" means >=