Searching in an array for numbers with each element +1 or -1 of preceding element [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 8 years ago.

Improve this question

An array of integers contains elements such that each element is 1 more or less than its preceding element. Now we are given a number, we need to determine the index of that number's first occurrence in the array. Need to optimize linear search. Its not homework.

Answer 1

My algorithm would be like this:

1. p=0
2. if (A[p] == x) then idx=p and the algorithm is finished else goto next step
3. set p += |x-A[p]|
4. goto 2.

say A[p] > x. Then, since A items increase or decrease by 1, idx is for sure at least (A[p] - x) index away from p. Same principle goes for A[p] < x.

int p=0, idx=-1;
while (p<len && p>=0)
   if (A[p]==x)
       idx = p;
   else
       p+= abs(x-A[p]);

Time complexity: The worst case would be O(n). I expect the average case to be better than O(n) ( I think it's O(log n) but not sure about it). Running time: Definitely better than linear search for all cases.

Answer 2

You can't be faster than linear. The following code should be as fast as you can go:

int findFirstIndex(int num, int[] array) {
     int i = 0;
     while (i< array.length)
          if (array[i] == num) return i;
          else i += abs(array[i] - num)
     return -1
}

But it's still O(array.length) in the worst case. Think for example if you are looking for 1 in an array containing only 0. Then, you can't skip any position.

Answer 3

Start from first position; now consider the difference between the searched number N and first number. if array[0] == N then we finished; otherwise we have to jump of abs(array[0] -N ) positions; now just repeat this until the end of the array.