Given a sorted array with n elements and element x that is inside the array at position k, find k in O(min(logk, log(n-k)))
Check the first element.  Then check the last.  Then the second, then the second to last, then the fourth, then the fourth to last, then the eighth, and so on.  Stop upon bounding the location of x to a region at the front or back of the list.

Once you've bounded it you can just do a binary search.

Can you see why this works?