Finding an element in an array where consecutive elements differ by 1 [closed]

It's difficult to tell what is being开发者_如何学JAVA asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 11 years ago.

There is an array and the distance between any two consequent elements is one (+1/-1). How will you find an element in it. Can it be done in less than O(n) time

---

Simply start in first position; now consider the difference bewteen the searched number m; if array[0] == m then we finished; otherwise we have to jump of abs(array[0] - m) positions; now just repeat this until the end of the array.

However, in the worst case we can't do better than O(n), just consider this case, we want to find 11:

10 9 8 9 8 9    10 9 8 9 8 9    10 9 8 9 8 9    10 9 8 9 8 9

---

Here's a simple idea that should help you think about the problem.

If you are looking for x and abs(x-array[0]) == k, then you may as well jump to array[k].

Think about this and you will have your algorithm.

Now, think about the worst possible case for this algorithm. Can you make it so that most entries have to be checked? (HINT: yes)