The problem statement should say the solution should be in the order of log(n). Otherwise, it is a very trivial problem since we can just find the index of the key in the input array and return which just takes o(n).