Question: Given an
array where two neighboring elements are adjacent (in absolute difference 1),
can you write an algorithm to search an element in the array and return its
position? If the element appears multiple times, please return the first
occurrence.

For example, if
given the array {4, 5, 6, 5, 6, 7, 8, 9, 10, 9} and an element 9, the element
appears twice in the array, and the first occurrence is at position 7.

Analysis: The most
simple and straightforward solution is to traverse the array and compare
elements one by one. This strategy works for every array, and it does not
utilize the property of the array where two neighboring elements are in
absolute difference 1.

Let's try to search
the first 9 from the array {4, 5, 6, 5, 6, 7, 8, 9, 10, 9}. Firstly we are at
position 0 where the element 4 is. The difference between 9 and 4 is 5, so we
move to the position 5. Why? Because the absolute difference between two neighboring
elements is 1. If the numbers in the array is increasingly sorted, the element
at position 5 is 9. If some elements decrease, 9 should sit on the right of
position 5. Therefore, 5 is the leftmost possible position of the element 9.

It's 7 at position
5. The difference between 7 and 9 is 2, so we move to right by distance 2 to
the position 7, where the first occurrence of 9 has been found.

We can summarize the
solution: We begin from the first element of the element, and compare it with
the given number. If the absolute difference is n,
move to the right by distance n. Then we
compare the current visited element. Repeat until the given element is found,
or the position is beyond the length of the array when the given element is not
available.

The solution can be
implemented in C/C++ as below:

int
findFirst(int*
nums, int
length, int target)

{

if (nums == nullptr || length <= 0)

return -1;

int index = 0;

while (index < length && nums[index] != target)

{

int delta = target - nums[index];

index += abs(delta);

}

if (index < length)

return index;

return -1;

}

{

if (nums == nullptr || length <= 0)

return -1;

int index = 0;

while (index < length && nums[index] != target)

{

int delta = target - nums[index];

index += abs(delta);

}

if (index < length)

return index;

return -1;

}

More coding interview questions are discussed
in my book< Coding Interviews: Questions, Analysis & Solutions>. You
may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of
this post. If you are going to use part of or the whole of this article in your
blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books,
please contact the author via zhedahht@gmail.com . Thanks.

Hi Harry,

ReplyDeleteThanks for sharing this interesting questions with super clean code. Actually I have two comments about this question:

1. It seems that the example is incorrect since element 8 only appears once.

2. I'm interested in the time complexity of the solution.

Thanks again for this awesome post!

Thanks for your comment. It's a typo. It should be element 9 which appears twice.

DeleteI'm also curious about the time complexity, but have not figured out. Can anyone help?

DeleteCorrect me if I'm wrong, if we have N numbers and the target number is T and the first number is F, then in the worst case, we may need N / |T - F| steps to reach it.

Deleteyou can consider o(n) as an upper bound since worst case you need to check all the elements. best case will be if the array is sorted in reverse natural order eg 10, 9, 8, 7, 6, 5, 4, 3, 2, 1. in that case if you're looking for 12, you will make 2, 4, 8... jumps so basically it's O(lg n)

Deleteso the complexity is somewhere between O(n) and O(lg n)

Hi Harry!

ReplyDeleteDid you figure out about the time complexity?

List of books to be referred for placement training preparation?

ReplyDeleteplacement training center in chennai

Why not start at the middle of the array?

ReplyDeleteHello my friend! I would like to tell you that this write-up is awesome, great written and include almost all important info. I recently came to know about http:www.yesiamhired.com, their Interview Tips are very effective.

ReplyDeleteInterview Tips

Integrated you software data at the best way of informatica system please call us on :- many new informatica interview questions references available online but this data warehouse interview questions one which is mentioned here is best in all possible ways. Always emphasize in getting this informatica questions

ReplyDeleteValid reasons for leaving a job?

ReplyDeletepart-time jobs

Awesome information, brain exercising post..

ReplyDeleteMoney Maker Research

ReplyDeleteGreat article Lot's of information to Read... Great Man Keep Posting and update to People..Thanks

free online tests

Great information, containing all information and also has a great impact on the new technology. Its very helpful for me.

ReplyDeleteWord ending with letter..

csharp code examples help you about c#

ReplyDeleteGreat information, containing all information and also has a great impact on the new technology. Its very helpful for me. Integrated you software data at the best way of informatica system.would like to tell you that this write-up is awesome, great written and include almost all important info.

ReplyDeleteStatic code testing

Nice post http://www.selfcarinsurance.com

ReplyDeleteThe time complexity is O(N). Assume the array is [4,3,4,3,4,3,4,3,...,4,3] and you are looking for 5. It is going to take you n/2 jumps whihc is O(n).

ReplyDelete