CODEWITHSUNDEEP
algorithm
anand
anand

Reputation: 11309

algorithm to search for an element in array

Here is another interview question

Array contains elements where next element can be either x+1 or x-1 if previous element is x.

Prev element = x
Next element = x+1/ x-1

Example: {2, 3, 4, 3, 2, 1, 0, -1, 0, 1, 2, 3, 2, 1}

If I need to search for 0 what is best algorithm we can choose?

If I sort it then it will be O(nlogn) and I can just traverse array in O(n) so O(n) is still better

Creating binary search tree will be again O(n) and search in BST is O(log) so still its O(n).

Its a random array and next element is +1 or -1 doesnot leads to any search pattern. If you guys can think of any search pattern that can be utilised here to perform better search then let me know.

Upvotes: 1

Views: 2958

Answers (1)

David Heffernan
David Heffernan

Reputation: 612844

The obvious thing to do is:

  1. Consider the first value, let's say the value is n. Is it 0?
  2. If yes, you are done.
  3. If not, step forward abs(n) elements, and go to step 1.

You can step over multiple elements because the absolute difference between two adjacent values is always 1.

So, given the array in your question, you do the following:

  • Item 0 is 2. That's not zero, and so you step to item 2.
  • Item 2 is 4. That's not zero, step forward 4 items to item 6.
  • Item 6 is 0. You are done.

Upvotes: 3

Related Questions