Finding an index in a sorted array

Question

Given a sorted array A[1...n] of keys, and another key, x, stored in A, show how to find the index, k, so that A[k] = x in time O(log(k)).

I know that a binary search on a sorted array would be completed in O(logn), on average, but what would be the best way to show a run time of O(logk), as described above, for a sorted array?
I appreciate any help.

Answer 1

Do an exponential search, starting with index m=1 then doubling m each time, until the array element at m is greater than x. Then, do the normal binary search on the subset of the array below the final m.

Answer 2

Binary search giving O(log N) is the standard approach. I'm not sure if O(log k) is a misprint, a semi-equivalence, or suggests "biasing" the search towards the low end o the range.

Maybe a binary search using a non-halfway midpoint.. since differential of log is log, perhaps using log() function to choose a midpoint at each iteration?