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.
