Hi,
I’m thinking about the problem in the title and I’m not sure it can always be done in O(logn).
If k is between the start and end values in the input list, we have two separate places to search for - somewhere on the left part and somewhere on the right part, judging min element as diferentiator.
The solution in the book is actually O(logn) time and you might take a look of that first 
I am not very sure about k value you mentioned here. You might want to explain it more.
Imagine this array:
10;20;30;40;50;60;70;80;-15;-5;5;15;25;35;45;55;65;75;85;90
Assuming k is 65, we have to search for him between 10-80 and 15 - 90.
Ohhh, I see, it’s binary search on two intervals: log(x)+log(y), where x+y<=n. This is <=log(n).