For an unsorted array, the best that you can do is linear time. No extra information you can get from the search space.