No. 58 - Search in Adjacent Numbers

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;
}

The source code with unit test cases is shared at http://ideone.com/zuwjui.

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.